However, sometimes all we have is a recursive definition and we do not know any direct formula for the general term of some series.
Also, recursive definitions are often much easier to find than a direct formula and also lend themselves to a nice method of
proof that the recursive definition is indeed correct.
We can count the number of derangements on n people as follows:
Take the person labelled 1. He can end up in any of n-1 seats. Suppose he ends up in seat i. Then
consider the person labelled i. For each of the n-1 possibilities for i,
the person labelled i now cannot sit in her original seat (number 1 is sitting there) and so can either end
up in seat 1 or one of the other n-2 seats.
#seats(people) | 1 | 2 | 3 | 4 | 5 | 6 | ... |
---|---|---|---|---|---|---|---|
#derangements | 0 | 1 | 2 | 9 | 44 | 265 | ... |
# Fixed points | 0 | 1 | 2 | 3 | Total |
---|---|---|---|---|---|
Perms | (2,3,1) (3,1,2) | (1,3,2) (3,2,1) (2,1,3) | - | (1,2,3) | 6 |
# Fixed points | 0 | 1 | 2 | 3 | 4 | Total=n! |
---|---|---|---|---|---|---|
# Perms{1} | 0 | 1 | 1 | |||
# Perms {1,2} | 1 | 0 | 1 | 2 | ||
# Perms {1,2,3} | 2 | 3 | 0 | 1 | 6 | |
# Perms {1,2,3,4} | 9 | 8 | 6 | 0 | 1 | 24 |
As used here | Vajda | Dunlap | Knuth | Definition | Description | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Phi Φ |
τ | τ | φ, α | (sqrt5 + 1)/2 = 1.6180339... | Koshy uses α (page 78) | |||||||||||||||
phi φ | -σ | -φ | -β | (sqrt5-1)/2= 0.6180339... | Koshy uses -β (page 78) | |||||||||||||||
abs(x) |x| | |x| | |x| | |x| | abs(x) = x if x≥0; abs(x) = -x if x<0 | the absolute value of a number, its magnitude; ignore the sign; | |||||||||||||||
floor(x) |__x__|; | [x] | trunc(x), not used for x < 0 | |__x__| | the nearest integer ≤ x. |
When x > 0, this is "the integer part of x" or "truncate x"
i.e. delete any fractional part after the decimal point. 3=floor(3)=floor(3.1)=floor(3.9), -4=floor(-4)=floor(-3.1)=floor(-3.9) | |||||||||||||||
round(x) [x] |
|
trunc(x + 1/2) | the nearest integer to x; trunc(x+0.5) | 3=round(3)=round(3.1), 4=round(3.9), -4=round(-4)=round(-3.9), -3=round(-3.1) 4=round(3.5), -3=round(-3.5) | ||||||||||||||||
ceil(x) |~x~|; | - | - | |~x~|; | the nearest integer ≥ x. | 3=ceil(3), 4=ceil(3.1)=ceil(3.9), -3=ceil(-3)=ceil(-3.1)=ceil(-3.9) | |||||||||||||||
fract(x) frac(x) | - | - | x mod 1 | x - floor(x) | the fractional part of x, i.e. the part of abs(x) after the decimal point | |||||||||||||||
|
|
|
|
|
nCr n choose r; the element in row n column r of Pascal's Triangle the coefficient of x^(r) in (1+x)^(n) the number of ways of choosing r objects from a set of n different objects. n≥0 and r≥0 (otherwise value is 0) |
Fibonacci-type series with the rule S(i) = S(i−1) + S(i−2) for all integers i:
i ... -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 ... Fibonacci
F(i)... -8 5 -3 2 -1 1 0 1 1 2 3 5 8 ... Lucas
L(i)... 18 -11 7 -4 3 -1 2 1 3 4 7 11 18 ... General Fib
G(a,b,i)... 13a-8b -8a+5b 5a-3b -3a+2b 2a-b -a+b a b a+b a+2b 2a+3b 3a+5b 5a+8b ...
Note that sequences may have many different types of recurrence that can be used to define them precisely. For example, the natural numbers 0,1,2,3,4,5,6,... are defined by each of the following
Linear homogenous recurrence relations with constant coefficients
...have the property that
P | Q | s_0 | s_1, s_2, ... | name | Generating Fn | OEIS |
---|---|---|---|---|---|---|
1 | 0 | k | k,k,k,k,k... | Constant series of k's | k/(1-x) | 1,1,1,1,1...A000012 2,2,2,2,2...A007395 3,3,3,3,3...A010701 4,4,4,4,4...A010709 5,5,5,5,5...A010716 ... |
-1 | 0 | 1 | -1,1,-1,1,-1,...(-1)^n,... | The Alternating Series of 1's | 1/(1+x) | A033999 |
1 | d | a | a+d,a+2d,a+3d,...,a+n d,... | Arithmetic Series | (a - a x + d x)/(x-1)^2 | 1,2,3,4,...,n,... A000027 0,2,4,6,8,...,2n,... A005843 1,3,5,7,9,...,2n+1,... A005408 0,3,6,9,12,...,3n,... A008585 1,4,7,10,13,...,3n+1,... A016777 ... |
r | 0 | a | a r, a r^2, a r^3,..., a r^n, ... | Geometric Series | a/(1-r x) | 1,2,4,8,16,32,...2^(n) A000079 1,3,9,27,81,...3^(n)A000244 3,6,12,24,48,96,...3 2^(n) A007283 5,10,20,40,80,... 5 2^(n) A020714 2,6,18,54,162,... 2 3^(n) A008776 4,12,36,108,324,... 4 3^(n) A003946 |
P | Q | s_0 | s_1 | s_2, s_3, ... | name | Generating Fn | OEIS |
---|---|---|---|---|---|---|---|
1 | 0 | 1,1,2,3,5,8... | Fibonacci F(n-1) | (1-x)/(1-x-x^2) | A000045 | ||
1 | 1 | 0 | 1 | 1,2,3,5,8... | Fibonacci F(n) | x/(1-x-x^2) | A000045 |
2 | 1 | 3,4,7,11,18,... | Lucas L(n) | (2-x)/(1-x-x^2) | A000032 | ||
F(0)+F(k) | F(1)+F(k+1) | ... | F(n) + F(n+k) | (F(k+1)+x(F(k-1)+1))/(1-x-x^2) | k=0: A006355, k=1:F(n+1) k=2: L(n+1), k=3: 2F(n+1) k=4: 3F(n+1), k=5: F(n)+L(n+1) k=6: | ||
a | b | a+b,a+2b,2a+3b,... | Generalised Fibonacci G(a,b,n) = F(n-1) a + F(n) b |
(a+(b-a)x)/(1-x-x^2) | G(a,b) | ||
0 | 1 | -1,2,-3,5,-8... | Fibonacci( - n ) | x/(1+x-x^2) | A039834 | ||
-1 | 1 | 1 | 0 | 1,-1,2,-3,5,-8... | F( 1 - n ) | (1+x)/(1+x-x^2) | |
a | b | a-b,-a+2b,2a-3b,-3a+5b,... | F( 1 - n ) a + F( -n ) b | (a+(a+b)x)/(1+x-x^2) | |||
1 | 2 | 0 | 1 | 1,3,5,11,21... | Jacobsthal J(n) (2^(n) - (-1)^(n))/3 |
x/(1-x-2x^2) | A001045 |
1 | 0 | 2,2,6,10,22,42... | 2 J(n-1) (2^(n) - (-1)^(n))2/3 |
(1-x)/(1-x-2x^2) | A078008 | ||
2 | 1 | 5,7,17,31... | Jacobsthal-Lucas 2^(n) + (-1)^(n) |
(2-x)/(1-x-2x^2) | A014551 | ||
a | b | 2a+b,2a+3b,6a+5b,... | 2a J(n-1) + b J(n) | (a+x(b-a))/(1-x-2x^2) | |||
2 | 1 | 0 | 1 | 2,5,12,29... | Pell Denominators of CF convergents to √2 |
x/(1-2x-x^2) | A000129 |
1 | 1 | 3,7,17... | Numerators of CF convergents to √2 | (1-x)/(1-2x-x^2) | A001333 | ||
1 | 0 | 1,2,5,12,29... | Pell(n-1) | (1-2x)/(1-2x-x^2) | A000129 | ||
2 | 2 | 6,14,34... | Companion Pell, Pell-Lucas | (2-2x)/(1-2x-x^2) | A002203 | ||
a | b | a+2b,2a+5b,5a+12b,.. | Pell(n) a + Pell(n+1) b | (1+(b-2a)x)/(1-2x-x^2) | |||
2 | -1 | 0 | 1 | 2,3,4,5... | the whole numbers | x/(1-2x+x^2) | A000027 |
1 | 0 | -1,-2,-3,-4,-5... | the negative numbers | (-x)/(1-2x+x^2) | A001478 | ||
0 | 2 | 4,6,8... | the even numbers | (2x)/(1-2x+x^2) | A005843 | ||
0 | 3 | 6,9,12,15... | 3n the sum of 3 consecutive integers |
3/(1-2x+x^2) | A008585 | ||
1 | 3 | 5,7,9... | the odd numbers | (1+x)/(1-2x+x^2) | A005408 | ||
2 | 6 | 10,14,18,22.. | 4n+2 Numbers not the side of any primitive Pythagorean triangle. The sum of 4 consecutive numbers. |
(2(5-3x))/(1-2x+x^2) | A016825 | ||
a | b | 2b-a,3b-2a,4b-3a... | n b - (n-1) a | (a+(b-2a)x)/(1-2x+x^2) | |||
a | a+d | a+2d, a+3d,...,a + n d, ... | Arithmetic Series | (a-x(a-d))/(x-1)^2 = (a-ax+dx)/(1-2x+x^2) | |||
3 | 1 | 0 | 1 | 3,10,33,109... | Ratios of terms are CF convergents to (3+sqrt13)/2 | x/(1-3x-x^2) | A006190 |
1 | 0 | 1,3,10,33,109... | Ratios of terms are CF convergents to (3+sqrt13)/2 | (1-3x)/(1-3x-x^2) | A006190 | ||
3 | -1 | 0 | 1 | 3,8,21,... | F(2n) = F(n+1)^2 - F(n-1)^2 = ( F(n+2)^2 - F(n-2)^2 )/3 = ( F(n+3)^2 - F(n-3)^2 )/8 = ... |
x/(1-3x+x^2) | A001906 |
1 | 0 | -1,-3,-8,-21,... | F(2 - 2n ) = - F( 2 n - 2 ) | (1-3x)/(1-3x+x^2) | (A001906) | ||
1 | 2 | 5,13,34,89... | F(2n+1) = F(n)^2 + F(n+1)^2 | (1-x)/(1-3x+x^2) | A001519 | ||
5 | 10 | 25,65,170,... | L(n)2 + L(n+1)2 = 5 F(2n+1) = 5 F(n)2 + 5F(n+1)2 |
(5(1-x))/(1-3x+x^2) | A106729 | ||
2 | 3 | 7,18,47,123... | L(2n) | (2-3x)/(1-3x+x^2) | A005278 | ||
1 | 4 | 11,29,76,199... | L(2n+1) | (1+x)/(1-3x+x^2) | A002878 | ||
a | b | 3b-a,8b-3a,21b-8a... | F(2n) b − F(2n −2) a | (a+(b-3a)x)/(1-3x+x^2) | |||
3 | -2 | 0 | 1 | 3,7,15,31,63... | 2^n-1 | x/(1-3x+2x^2) =x/((1-2x)(1-x)) |
A000225 |
2 | 3 | 5,9,17,33,65... | 2^n+1 | (2-3x)/(1-3x+2x^2) | A000051 | ||
a | b | 3b-2a,7b-6a,15b-14a... | (2^n - 1) b - (2^n - 2) a | (a+(b-3a)x)/(1-3x+2x^2) | |||
4 | 1 | 0 | 1 | 4,17,72... | Denominators of CF convergents to √5 =Fib(3n)/2 |
(x)/(1 - 4 x - x^2) | A001076 |
1 | 2 | 9,38,161... | Numerators of CF convergents to √5 = Lucas(3n)/2= Fib(3n)/2+F(3n-1) |
(1 - 2 x)/(1 - 4 x - x^2) | A001077 | ||
F(0)=0 | F(3)=2 | 8,34,144... | F(3n) | (2 x)/(1 - 4 x - x^2) | A014445 | ||
F(1)=1 | F(4)=3 | 13,55... | F(3n+1) | (1 - x)/(1 - 4 x - x^2) | A033887 | ||
F(2)=1 | F(5)=5 | 21,89... | F(3n+2) | (1 + x)/(1 - 4 x - x^2) | A015448 | ||
a | b | a+4b,4a+17b,17a+72b... | ( F(3n) a + F(3n+3) b )/2 | (a + (b - 4a) x)/(1 - 4 x - x^2) | |||
6 | -1 | 0 | 1 | 6,35,204... | Numbers n such that n2 is a Triangular number = Pell(2n)/2 |
( x )/(1 - 6 x + x^2) | A001109 |
0 | 2 | 12,70,408... | Pell(2n), the even Pell numbers | ( 2 x )/(1 - 6 x + x^2) | A001542 | ||
1 | 5 | 29,169,985... | Hypotenuse, h, of Pythagorean triangles
with consecutive legs (a,a+1,h) Ratios of terms are convergents to CF [5; 1,4] = 3 + 2 √2 Pell(2n+1), the odd Pell numbers |
(1 - x)/(1 - 6 x + x^2) | A001653 | ||
a | b | −a+6b,−6a+35b,−35a+204b... | (a + (-6a+b) x)/(1 - 6 x + x^2) | ||||
7 | -1 | 0 | 1 | 7,48,329... | F(4n)/3 | (x)/(1 - 7 x + x^2) | A004187 |
a | b | 7b-a,48b-7a,... | (F(4n) b - F(4n-4) a )/(3) | (a + (b - 7a) x)/(1 - 7 x + x^2) |
P | Q | s0 | s1 | name | Gen. Fn. |
---|---|---|---|---|---|
L(k) | (-1)k | F(i) | F(i+k) | F(kn+i);i=0..k-1 | (F(i) + ( F(k+i) - F(i)L(k) ) x)/(1 - L(k) x - (-1)^k x^2) |
L(i) | L(i+k) | L(kn+i);i=0..k-1 | (L(i) + ( L(k+i) - L(i)L(k) ) x)/(1 - L(k) x - (-1)^k x^2) | ||
a | b | (a + ( b - a L(k) ) x)/(1 - L(k) x - (-1)^k x^2) | |||
n | 1 | 0 | 1 |
Denominators of CF convergents of (n + \sqrt(n^2+4)) /2
whose CF is [n; n,n,n,n,...] |
( x )/(1 - n x - x^2) |
1 | n | Numerators of CF convergents of CF [n; n,n,n,n,...] |
( 1 )/(1 - n x - x^2) | ||
P | Q | a | b | General second order recurrence | ( a - (a P - b) x )/(1 - P x - Q x^2) |
P | Q | R | s0 | s1 | s2 | s3 ... | name | Gen. Fn. | OEIS |
---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 0 | 0 | 1 | 0,1,1,1,2,2,3,4,5,7... | Padovan | ( x^2)/(1 - x^2 - x^3) | A000931 |
0 | 2 | 1 | 0 | 1 | 1 | 2,3,5,8,13... | Fibonacci F(n+3)=2F(n+1)+F(n) Vajda-8 with m=3) |
(x )/((1 - x - x^2) ) | A000045 |
1 | 1 | 1 | 0 | 0 | 1 | 1,2,4,7,13,24... | Tribonacci numbers | ( x^2)/(1 - x - x^2 - x^3) | A000073 |
2 | 0 | -1 | 0 | 1 | 1 | 2,3,5,8,13... | Fibonacci B&Q(2003) Identity 16 |
(x )/((1 - x - x^2 )) | A000045 |
2 | 2 | -1 | 0 | 1 | 1 | 4,9,25,64... | F(n)2 | ( x - x^2)/(1 - 2 x - 2 x^2 + x^3)
= ( x ( 1 - x ))/(( 1 + x )( 1 - 3 x + x^2)) |
A007598 |
0 | 1 | 2 | 6,15,... | F(n)F(n+1)=(F(n+2)^(2)-F(n-1)^(2))/4 | ( x )/(1 - 2 x - 2 x^2 + x^3) | A001654 | |||
0 | 2 | 3 | 10,24,... | F(n)F(n+2) | ( 2 x - x^2)/(1 - 2 x - 2 x^2 + x^3) | A059929 | |||
0 | 3 | 5 | 16,39,... | F(n-1)F(n+2) =F(n+1)^(2)-F(n)^(2) | ( 3 x - x^2)/(1 - 2 x - 2 x^2 + x^3) | A226205 | |||
0 | 4 | 8 | 24,60,160,... | F(n+3)^(2) - F(n)^2 = 4 F(n) F(n+1) |
( 4 x )/(1 - 2 x - 2 x^2 + x^3) | A192883 | |||
0 | 5 | 8 | 26,63,... | F(n-2)F(n+2) | ( 5 x - 2 x^2)/(1 - 2 x - 2 x^2 + x^3) | A192883 | |||
3 | 8 | 25 | 63,168... | F(n+5)^(2)-F(n)^(2) | ( 3 + 2x + 3x^2)/(1 - 2 x - 2 x^2 + x^3) | ||||
4 | 1 | 9 | 16,49,121... | L(n)2 | ( 4 - 7 x - x^2)/(1 - 2 x - 2 x^2 + x^3) | A001254 | |||
2 | 3 | 12 | 28,77,198... | L(n)L(n+1) | ( 2 - x + 2 x^2)/(1 - 2 x - 2 x^2 + x^3) | A215602 | |||
a | b | c | −a+2b+2c, −2a+3b+6c, −6a+10b+15c ... | −F(n)F(n+1)a +F(n+2)G(b,c,n+1) | ( a + ( b-2a ) x - ( 2a+2b-c ) x^2)/(1 - 2 x - 2 x^2 + x^3) | ||||
0 | a | b | 2a+2b, 3a+6b, ... | F(n)G(a,b,n-1) | ( a x + ( b - 2 a )x^2)/(1 - 2 x - 2 x^2 + x^3) | ||||
a2 | b2 | (a+b)2 | (a+2b)2, (2a+3b)2 ... | G(a,b,n)2 | ( a^(2) + (b^(2) - 2 a^(2)) x - (a - b)^(2) x^2)/(1 - 2 x - 2 x^2 + x^3) | ||||
ab | b(a+b) | (a+b)(a+2b) | (a+2b)(2a+3b), ... | G(a,b,n) G(a,b,n+1) =Fn-1Fna2 + (FnFn+1+Fn-12)ab +FnFn+1b2 |
( a b - b ( a - b) x + a (a - b) x^2)/(1 - 2 x - 2 x^2 + x^3) | ||||
3 | -3 | 1 | 0 | 1 | 2 | 3,4,5... | Natural Numbers | ( x )/((x - 1)^(2)) | A000017 |
0 | 1 | 3 | 6,10,15... | Triangular Numbers = n ( n + 1 ) / 2 | ( x)/((x - 1)^(3)) | A000217 | |||
0 | 2 | 6 | 12,20,30... | Pronic Numbers = n ( n + 1 ) | ( 2x)/((x - 1)^(3)) | A002378 | |||
0 | 1 | 4 | 9,16,25... | Square Numbers = n2 | ( x (x + 1))/((x - 1)^(3)) | A000290 | |||
0 | 1 | 5 | 12,22,35... | Pentagonal Numbers =n ( 3 n - 1) / 2 |
( x (2 x + 1))/((x - 1)^(3)) | A000326 | |||
0 | 1 | 6 | 15,28,45... | Hexagonal Numbers =n ( 2 n - 1) / 2 |
( x (3 x + 1))/((x - 1)^(3)) | A000384 | |||
0 | 1 | N | 3N-3,6N-8,10N-15,... | Polygonal Numbers Figurate Numbers with N sides= n [ N (n-1) /2 - (n-2) ] |
( x + (N-3) x^2)/((x - 1)^(3)) | ||||
1 | 4 | 10 | 19, 31, 46, ... | Centred Triangular Numbers =½ (3 n^(2) - 3 n + 2) = 1 + 3 n(n-1)/2 |
( x (1 + x + x^2))/((x - 1)^(3)) | A005448 | |||
1 | 5 | 13 | 25,41,61, ... | Centred Square numbers = Hypotenuses h of Pythagorean triangles with sides (a, h-1, h) = 4 Triangular(n) + 1 = 2 n^(2) + 2 n + 1 |
( (1 + x)^( 2))/((x - 1)^(3)) | A001844 | |||
1 | 6 | 16 | 31, 51, 76, ... | Centred Pentagonal Numbers = ½ (5 n^(2) - 5 n + 2) |
( 1 + 3 x + x^2)/((x - 1)^(3)) | A005891 | |||
1 | 7 | 19 | 37, 61, 91, ... | Centred Hexagonal Numbers = ½ (6 n^(2) - 6 n + 2) = 1 - 3n + 3n2 |
( 1 + 4 x + x^2)/((x - 1)^(3)) | A003215 | |||
1 | 1+k | 1+3k | 1+6k, 1+10k, 1+15k, ... | Centred Polygonal(k-gonal) Numbers = ½ (k n^(2) - k n + 2) |
( 1 + (k - 2) x + x^2)/((x - 1)^(3)) | ||||
7 | -7 | 1 | 0 | 3 | 20 | 119,696,... | Smallest leg,a, of Pythagorean triangles (a,a+1,h) |
( 3 - x)/(1 - 7 x + 7 x^2 - x^3) | A001652 |
1 | 8 | 49 | 288,1681,... | The rank of a triangle number which is also square | ( 1 + x)/((1 - x )( 1 - 6 x^2 + x^2)) | A001108 | |||
8 | -8 | -1 | 0 | 1 | 9 | 64,441... | F(2n)2 | ( x + x^2)/(1 - 8 x + 8 x^2 - x^3) =( x ( 1 + x ))/(( 1 - x )( 1 - 7 x + x^2 )) | A049684 |
12 | 22 | 52 | 169... | F(2n+1)2 | (1 - 4 x + x^2)/(1 - 8 x + 8 x^2 - x^3) | A081068 | |||
15 | -15 | 1 | 0 | 1 | 12 | 165, 2296, ... | Rank of Pentagonal Numbers that are Triangular | ( x (1 - 3x))/((1 - x)(1 -14x+x^2)) | A046174 |
0 | 1 | 20 | 285, 3976, ... | Rank of Triangular Numbers that are Pentagonal | ( x (1 + 5x))/((1 - x)(1 -14x+x^2)) | A046175 | |||
17 | 17 | -1 | 0 | 22 | 82 | 1156... | F(3n)2 | ( 4 x - 4 x^2)/(- 1 + 17 x + 17 x^2 - x^3) = ( 4 (x - 1) x)/(( 1 + x )( 1 - 18 x + x^2 )) |
A014729 |
12 | 32 | 132 | 3025... | F(3n+1)2 | ( - 1 + 8 x + x^2)/(- 1 + 17 x + 17 x^2 - x^3) | ||||
12 | 52 | 212 | 7921... | F(3n+2)2 | ( - 1 - 8 x + x^2)/(- 1 + 17 x + 17 x^2 - x^3) | ||||
35 | -35 | 1 | 1 | 36 | 1225 | 41616, ... | Square Triangular numbers | ( 1 + x )/((1 - x )( 1 - 34 x + x^2)) | A001110 |
195 | -195 | 1 | 0 | 1 | 210 | 40755, ... | Pentagonal Triangular numbers | (x( 1 + 15x) )/((x - 1 )( 1 - 194 x + x^2)) | A001110 |
9603 | -9603 | 1 | 1 | 9801 | 94109401 | 903638458801, ... | Square Pentagonal numbers | ( 1 + 198 x + x^2)/((1 - x )( 1 - 9602 x + x^2)) | A036353 |
P | Q | R | s0 | s1 | s2 | series | Gen.Fn. | ||
---|---|---|---|---|---|---|---|---|---|
L(2k)+(-1)k | -L(2k)-(-1)k | (-1)k | F(i)2 = a | F(k+i)2 = b | F(2k+i)2 = c |
F(kn+i)2 | ( a - ( a P - b) x - ( a Q + b P - c ) x^2)/((x + (-1)^(k))(x^2 - L(2k) x + 1)) | for i in {0..k-1} | |
P | Q | R | a | b | c | General Third order Recurrence | ( a - ( a P - b) x - ( a Q + b P - c ) x^2)/(1 - P x - Q x^2 - R x^3) |
P | Q | R | S | s0 | s1 | s2 | s3 | series | name | Gen. Fn. | OEIS |
---|---|---|---|---|---|---|---|---|---|---|---|
3 | 6 | -3 | -1 | 0 | 1 | 1 | 8 | 8,27,125... | F(n)3 | ( 1 - 2x - x^2 )/(1 - 3 x - 6 x^2 + 3 x^3 + x^4)
= ( 1 - 2x - x^2 )/(( x^2 - x - 1 )( x^2 + 4 x - 1 )) |
A056570 |
0 | 0 | 0 | 1 | 3,15,60,260 | F(n-1)F(n)F(n+1)/2 | ( 1 )/(1 - 3 x - 6 x^2 + 3 x^3 + x^4) | A001655 | ||||
0 | 0 | 0 | 2 | 6,30,120,520 | F(n-1)F(n)F(n+1) | ( 2 )/(1 - 3 x - 6 x^2 + 3 x^3 + x^4) | A065563 | ||||
0 | 0 | 1 | 2 | 12,45,200... | F(n)2F(n+1) | ( x - x^2 )/(1 - 3 x - 6 x^2 + 3 x^3 + x^4) | A066258 | ||||
0 | 0 | 3 | 10 | 48,195,840... | F(n-1)F(n)F(n+2) | ( 3 x + x^2 )/(1 - 3 x - 6 x^2 + 3 x^3 + x^4) | A220362 | ||||
0 | 2 | 0 | 10 | 24,130,504... | F(n-2)F(n)F(n+2) | ( 2 - 6 x - 2 x^2 )/(1 - 3 x - 6 x^2 + 3 x^3 + x^4) | A226958 | ||||
1 | 0 | 6 | 15 | 80,312,1365... | F(n-2)F(n)F(n+1) | ( x - 3 x^2 )/(1 - 3 x - 6 x^2 + 3 x^3 + x^4) | A220360 | ||||
0 | -3 | 5 | 0 | 39,105,544 | F(n-2)F(n)F(n+3) | ( 3 - 9 x - 2 x^2 )/(1 - 3 x - 6 x^2 + 3 x^3 + x^4) | |||||
1 | 1 | 2 | 9 | 35,152... | F(n)3+F(n+1)3 | (1 - x - 3 x^2 - 3 x^3 )/(1 - 3 x - 6 x^2 + 3 x^3 + x^4) | A110224 | ||||
1 | 9 | 28 | 133 | 539,2322.. | F(n)3+F(n+2)3 | (1 + 6 x - 5 x^2 - 2 x^3 )/(1 - 3 x - 6 x^2 + 3 x^3 + x^4) | A226976 | ||||
F(n)3+F(n+k)3 | ((1 - 2x - x^2)(1 + x^k))/(1 - 3 x - 6 x^2 + 3 x^3 + x^4) | ||||||||||
F(n)F(n+a)F(n+b) | ( (-1)^(b)( F(a+1)F(b+1) x + G(-L(b),F(b-2),a) x^2 - F(b-1)F(a-1) x^3 ))/(1 - 3 x - 6 x^2 + 3 x^3 + x^4) |
G(x) = | ∞ Σ i=0 | S(i) x^i | = S(0) + S(1) x + S(2) x^2 + S(3) x^3 + ... |
To shift to the right (insert a 0 at the start of the series so all other terms have an index increased by 1),
multiply the GF by x; to shift to the left, divide by x.
There is much more on GFs on my Fibonomials page.
Fibonacci(n) 0,1,1,2,3,... | (x)/(1 - x - x^2) |
Fibonacci(2n) 0,1,3,8,21,... | (x)/( x^2 - 3 x + 1 ) |
Fibonacci(2n+1) 1,2,5,13,... | (1 - x)/( x^2 - 3 x + 1 ) |
Fibonacci(3n) 2,8,34,144,... | (2 x)/( 1 - 4 x - x^2 ) |
Fibonacci(3n+1) 1,3,13,55,... | (1 - x)/( 1 - 4 x - x^2 ) |
Fibonacci(3n+2) 1,5,21,89,... | (x + 1)/( 1 - 4 x - x^2 ) |
Fibonacci(k n) | (F(k) x)/(1 - L(k) x + (-1)^k x^2) |
Fibonacci(n)2 0^(2),1^(2),1^(2),2^(2),3^(2),... | (x - x^2 )/(1 - 2 x - 2 x^2 + x^3) |
Fib(n)Fib(n+1) 1×1,1×2,2×3,3×5,... | ( x)/( 1 - 2 x - 2 x^2 + x^3) |
Fibonacci(n)3 0^(3),1^(3),1^(3),2^(3),3^(3),... | (x-2x^2-x^3)/(1-3x-6x^2+3x^3+x^4) |
Lucas(n) 2,1,3,4,7,... | (2 - x)/(1 - x - x^2) |
Lucas(2n) 2,3,7,18,... | (2 - 3 x)/( x^2 - 3 x + 1 ) |
Lucas(2n+1) 1,4,11,29,... | (1 + x)/( x^2 - 3 x + 1 ) |
Lucas(3n) 2,4,18,76,... | (2 - 4 x)/( 1 - 4 x - x^2 ) |
Lucas(3n+1) 3,11,47,199,... | (3 x + 1)/( 1 - 4 x - x^2 ) |
Lucas(3n+2) 2,4,18,76,... | (3 - x)/( 1 - 4 x - x^2 ) |
Lucas(k n) | (2 - L(k) x)/(1 - L(k) x + (-1)^k x^2) |
Lucas(n)^(2) 2^(2),1^(2),3^(2),4^(2),... | (4 - 7 x - x^2)/(1 - 2 x - 2 x^2 + x^3 ) |
Lucas(n)Lucas(n+1) 2×1,1×3,3×4,4×7,... | (2 - x + 2 x^2)/(1 - 2 x - 2 x^2 + x^3 ) |
Lucas(n)^(3) 2^(3),1^(3),3^(3),4^(3),... | (8-23x-24x^2+x^3)/(1-3x-6x^2+3x^3+x^4) |
G(a,b,n) a,b,a+b,a+2b,... | (a + (b - a) x)/( 1 - x - x^2 ) |
G(a,b,2n) a,a+b,2a+3b,... | (a + (b - 2a) x)/( x^2 - 3 x + 1 ) |
G(a,b,2n+1) b,a+2b,3a+5b,... | (b + (a - b) x)/( x^2 - 3 x + 1 ) |
G(a,b,3n) a,a+2b,5a+8b,... | (a + (2 b - 3 a) x)/( 1 - 4 x - x^2 ) |
G(a,b,3n+1) a+b,3a+5b,13a+21b,... | (b + (2 a - b) x )/( 1 - 4 x - x^2 ) |
G(a,b,3n+2) a,a+2b,5a+8b,... | (a + b + (b - a) x )/( 1 - 4 x - x^2) |
G(a,b,kn) | (a+(F(k)b-F(k+1)a)x)/(1-L(k)x+(-1)^k x^2) |
G(a,b,n)^(2) a^(2),b^(2),(a+b)^(2),... | (a^(2)+(b^(2)-2a^(2))x-(a-b)^(2)x^2)/(1-2x-2x^2+x^3) |
G(a,b,n)G(a,b,n+1) ab,b(a+b), (a+b)(a+2b),... | (ab + b(b-a)x + a(a-b)x^2)/(1-2x-2x^2+x^3) |
The GF of 1,2,5,13,... is that of
Fib(2n+1)
which is
(1 - x)/(x^2 - 3 x + 1)>
so 1,0,2,0,5,0,13,... has GF
(1 - x^2)/(x^4 - 3 x^2 + 1)
To insert an extra 0 at the start, multiply the GF by x.
So the GF for the odd-indexed Fibonacci numbers only in their correct positions in the Fibonacci series
with Fib(2n+1) is the coefficient of x^(2n+1)
is therefore x (1 - x^2)/(x^4 - 3 x^2 + 1)
for the series 0,1,0,2,0,5,0,13,... .
Adding these two GFs, that is, for Fib(2n) as the coefficient of x^(2n)
and Fib(2n+1) as the coefficient of x^(2n+1)
should then give the complete
Fibonacci series GF:
0,0,1,0,3,0,8, 0,21, ... +We can check that x^2/(x^4 - 3 x^2 + 1) + x (1 - x^2)/(x^4 - 3 x^2 + 1) = x/(1 - x - x^2)
0,1,0,2,0,5,0,13, 0, ...
0,1,1,2,3,5,8,13,21,...
Multiplying a GF by a constant k multiples all the members of the series by k.
A series formed by adding two series S and T element-wise to form the series {S(n)+T(n) for n=1,2,3,...},
has a GF which is the sum of the two separate GFs for example for a Fib_(n-1) + b Fib_n = G(a,b).
|
Exponential Generating Functions For Fibonacci Identities C Church and Marjorie Bicknell, Fib Q vol 11 (1983) 275-281 | ||||||
|
Exponential Generating Functions For Fibonacci Identities C Church and Marjorie Bicknell, Fib Q vol 11 (1983) 275-281 |
© 2013-2024 Dr Ron Knott