When `a != 0`, there are two solutions to `ax^2 + bx + c = 0` and they are

`x = (-b +- sqrt(b^2-4ac))/(2a) .`

Recurrence Relations and Generating Functions

This page is an extension to my Fibonacci and Phi Formulae with an introduction to Recurrences and Generating Functions.

Contents of This Page


Introduction to Recurrences

When we have a series or numbers, a formula for the general term makes it easy to compute any term directly. However, sometimes it is not easy to find such a formula but it is much easier to find how one term relates to some of the earlier terms.
For instance, the Fibonacci numbers `0,1,1,2,3,5,8,13,...` have a simple description where each term is related to the two terms before it. If `F(n)` is the `n`th term of this series then we have `F(n) = F(n-1) + F(n-2)`. This is called a recursive formula or a recurrence relation since it needs earlier terms to have been computed in order to compute a later term.
A recurrence formula also needs some initial terms since at the moment we could start form any two numbers and get very difference series:
2, 1 leads to 2+1=3, 1+3=4, 7, 11, .... called the Lucas Numbers whereas
0, 1 leads 1, 1, 2, 3, 5, ... the Fibonacci Numbers.
So the complete recurrence relation is
`F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) if n >= 2 `
There is a formula for F(n) which involves only n:
`F(n) = (Phi^n - (-phi)^n) / sqrt5`
F(n) =  Phin – (–phi)n

√5
where Phi=(√5 + 1)/2 and phi=(√5 - 1)/2
Both the recurrence formula and the direct formula are enough to describe any term in the Fibonacci series but the difference is seen is we need to find, say, F(100).
Though the recurrence formula is easy, we need to compute F(99) and F(98) which in turn need F(97) and so on. Indeed we need to find every number from F(0) up to F(97)before we can compute F(100). The direct formula does not have this disadvantage.

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.

Some Examples

Derangements
Suppose n people sit in a circle and they play a variation of Musical Chairs. When the music starts they all start walking round the circle of chairs but when it stops they all take a seat as quickly as they can. In this variation, no one is left without a seat!
In how many ways can everybody be sitting in a new seat?

There are n! ways to seat n people in n seats since the first person has a choice on n seats, the second a choice of the remaining n-1, the third n-2 and so on until the last person has just 1 choice. So in total there are
n×(n-1)×(n-2)×...×3×2×1 permutations
This is called n factorial and often written as n ! .
There is obviously only 1 way that everybody can be sitting in the same seat as when they started.
There are n! ways of seating n people in n seats, so then why is answer to this puzzle not n! - 1?
Because that just excludes the permutation where everyone is seated in the same seat as originally.
Removing that one case is just the number of permutations where at least 1 person is not sitting in their original seat.
Our puzzle here puzzle asks for everybody to be sitting in a different seat.
Such a permutation of the n numbers (people) where no number (person) is in his original position is called For instance, label the seats 1 to n and give each person a label which was the original seat he or she was sitting in. When the music stops, we go round the seat in order from 1 to n and note the label of the person sitting there. Thus we might have 3 people starting as (1,2,3) and ending up as (3,2,1) but in this case, the second item, the person sitting in the second seat, is person 2 -- so he is sitting in his original seat and this is not a derangement.
However, the final seating order of (2,3,1) is a derangement as it means that
  1. the first seat is occupied by person 2 (originally sitting in seat 2)
  2. the second seat has the person originally in seat 3
  3. the third seat has the person originally in seat 1
For 3 people there are only two derangements: (2,3,1) and (3,1,2).
How many are there for 4 people? 5 people?

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.

If D(n) counts the number of derangements of n people we have the formula:
D(n) = (n – 1) ( D(n-1) + D(n-2) )
So, since with 1 person there are no derangements, and with 2 people there is just 1 derangement. So, by the recurrence formula above we have
D(3) = 2 ( D(2)+D(1) ) = 2(1+0) = 2, and so we know we found all the solutions in the above example with 3 people.
We have the counts of the number of derangements of n people as the following series:
#seats(people)123456...
#derangements012944265...
There is a direct formula for D(n) too:
D(n) = n!/2!n!/3! + n!/4! – ... + (-1)n), n>2     
Note that the recursion formula is usually not unique. Here we can also express D(n) as
D(n) = n D(n-1) + (-1)n

/ Things to do /

  1. Write out all the 9 derangements of 4 numbers.
    1. Calculate D(4) using the factorial formula.
    2. Is D(4) easier to calculate using the factorial formula or using the recurrence relation?
    3. What about D(10)? Which is easier in this case?
  2. Check that D(n) = n D(n-1) + (-1)n gives the same results as in the table above for n=2, 3 and 4. What is the missing part of this formula - that is, how many initial terms are needed to completely fix the numbers in this series?
  3. Can you find a proof for D(n) = n D(n-1) + (-1)n?
    1. What is the probablility that with 4 people none are sitting in the same seat when the music stops?
    2. What about with 5 people?
    3. Draw a graph of the probablility of getting a derangement with n people for n from 2 to 12
    4. What does this suggest about the probability of a derangement as the number of people increases?

Variations

Our puzzle was presented as Musical Chairs. Here are some other variations of the same puzzle:
  1. Secret Santa A week before the office Christmas Party, everyone buys one present, wraps it and puts it in Santa's Sack under the Christmas Tree.
    At the Party, everyone picks one present at random from the sack. No one wants their own present so what is the probability that everyone picks a different present to the one they put in?
    Practical solution 1: everyone picks a random name from a hat and buys a present for that named person
    Practical solution 2: If you pick your own, put it back and pick another.
  2. The distracted secretary at a busy office is so busy that, given n individually addressed letters to put into the n addressed envelopes to get ready for posting, gets everything wrong, so that no letter gets put in its correct envelope!
    Practical solution: Buy envelopes with a clear window and fold the letter so the addressee shows through the window
  3. The cloakroom (American: checkroom) attendant at a theatre inadvertently opens a window on a windy day and all the tickets for the items the audience have left there get blown off their pegs and mixed up. The attendant puts the tickets back on the pegs at random. What is the probablilty no one gets their own belongings back after the show?
    Practical solution: make sure the tickets are given out in order and the clothes put in order on the pegs!
  4. No snap! Two new packs of cards are bought, both having all the cards in order of suit and pip. One is shuffled and given to someone else to deal, one is left in order. The two packs are then dealt simultaneously, one card at a time, each pack onto its own pile.
    What is the probability that no one shouts "Snap!" during the whole game.
    Does it matter is one pack is in order?
    In the game of snap, when two identical cards appear as two players deal their decks, the first to shout "Snap" wins the cards. The one with the most cards at the end of the game, when all cards have been dealt, is the winner.
    Practical solution: just shuffle two packs of cards as the answer is identical!

/ Things to do /

  1. In our derangements, all n items get moved to a different place.
    But given a permutation of items, we can count how many remain fixed and how many move.
    Take the 4×3×2=24 permutations of {1,2,3,4}. Count how many items in each permutation are fixed (from 0 to 4) and make a table of these frequencies. A derangement is a permutation with no fixed points.
    For instance, with 3 numbers {1,2,3} we have the following:
    # Fixed points0123Total
    Perms(2,3,1)
    (3,1,2)
    (1,3,2)
    (3,2,1)
    (2,1,3)
    -(1,2,3)6
    Extend the table to several more rows and investigate the patterns here.
    As a check, here are the frequencies of permuations of {1,2,3,4} with their fixed point counts:
    # Fixed points01234Total=n!
    # Perms{1}011
    # Perms {1,2}1012
    # Perms {1,2,3}23016
    # Perms {1,2,3,4}9860124
    Try to find recurrence relations to describe your numbers or explicit formulae.

Types and Properties of a Recurrence

Recursive definitions and recurrences have been used for a long time by mathematicians. Here are a few terms used to describe them:
the Order of a recurrence
This is the earliest number of previous terms we need to find any term.
In s(n) = s(n-2 + s(n-4) we need the 4th term before so the order of this recurrence is 4.
the Degree of a recurrence
If we have s(n) = s(n-1)2 + 1 then one term involves squares of an earlier term.
In the sum of terms, the highest degree of a term is the degree of the recurrence.
This example has a term of degree 2 but the Fibonacci recurrence is of degree 1.
a Linear recurrence
A recurrence of degree 1 is a linear recurrence, such as P(n) = 2 P(n-1) + P(n-2) .
a Homogeneous recurrence
If the recurrence (without initial conditions) applies to the sequence consisting only of 0's then the recurrence is homogeneous.
Thus s(n) = s(n-1)2 - s(n) and F(n)=F(n-1)+F(n-2) are both homogeneous but s(n) = s(n-1)2 + 1 is not.
with Constant coefficients
If all the terms in a recurrence involve only previous terms and a constant multiplier, then the recurrence has constant coefficients.
Thus P(n) = 2 P(n-1) + P(n-2) has constant coefficients (and is linear) but the derangement recurrence D(n) = n (D(n-1) + D(n-2)) has n as the multiplier of D(n-1) and D(n-2) so does not have constant coefficients.

Generating Functions

Many series have a very compact representation as the coefficients of a power series:
the series s0, s1,s1, ... ,sn, ... are the coefficients of x0, x1,x1, ... ,xn, ... . But the main advantage is where the power series itself is a rational form: a fraction made from two simple expressions in x. For example:
1 = 1 + x + x2 + x2 + ...
1 – x
so we say that the series (of coefficients) 1,1,1,1,1,... has generating function 1/(1–x).
1 = 1 + 2 x + 3 x2 + 4 x2 + ...
(1 – x)2
so the series of natural numbers 1,2,3,4,... has generating function 1/(1–x)2.
In the following, we often use GF as an abbreviation for Generating Function.

The relationship between Recurrences and Generating Functions

The interesting thing is that there is a simple relationship between the denominator of a GF and a recurrence relation which defines the same series. Here are some examples:
the series of natural numbers
1,2,3,4,...
has generating function
1/(1–x)2 = 1/(1 – 2 x + x2)
and it has the recurrence
sn = 2 sn-1 - sn-2
We can see the relationship more clearly if we rewrite the recurrence in this form:
sn - 2 sn-1 + sn-2 = 0
and compare that with the denominator of the GF, namely:
1 – 2 x + x2
This is a general principle!

Definitions and Notation

Beware of different golden ratio symbols used by different authors!
Where a formula below (or a simple re-arrangement of it) occurs in either Vajda or Dunlap's book, the reference number they use is given here. Dunlap's formulae are listed in his Appendix A3. Hoggatt's formula are from his "Fibonacci and Lucas Numbers" booklet. Full bibliographic details are at the end of this page in the References section.
As used hereVajdaDunlapKnuthDefinitionDescription
Phi
Φ
τ τφ, α
√5 + 1
2
= 1.6180339...
Koshy uses α (page 78)
phi
φ
–σ–φ–β
√5 – 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]
[ x +  1 ]
--
2
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
(n
r
)
(n
r
)
(n
r
)
(n
r
)
n!
--
r! (n – r)!
nCr
n choose r;
the element in row n column r of Pascal's Triangle
the coefficient of xr 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–10123456...
Fibonacci
F(i)
...–85–32–110112358...
Lucas
L(i)
...18–117–43–1213471118...
General Fib
G(a,b,i)
...13a–8b–8a+5b5a–3b–3a+2b2a–b–a+baba+ba+2b2a+3b3a+5b5a+8b...

Linear Recurrence Relations

These linear homogeneous recurrence relations with constant coefficients and their sequences listed here have some relationship to the Fibonacci numbers.
The "Fibonacci Rule" that we add the latest two numbers to get the next in a series, can be applied to starting values: But among the Fibonacci and Lucas and General Fibonacci series we can also find recurrence relationships which use other constant multiples of earlier values too.
If the next term is a sum of integer multiples of earlier terms then the recurrence is a linear recurrence. If the "earliest" term used to compute sn is sn-k, i.e. the previous k terms are used to compute the next, then the order of the recurrence is k.
A recurrence of order k needs k initial terms to define it completely.
Strictly, on this web page, we are looking at linear homogenous recurrence relations with constant coefficients and these terms are examined in the examples here:
Various forms of recurrence for the same sequence

Note that sequences may have many different types of recurrence that can be used to define them exactly. 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


A helpful page on recurrence relations on this page is Tanya Khovanova's Recursive Sequences

Order 2

These recurrence sequences are defined by 4 numbers: s0, s1 and P and Q, Q≠0 where sn = P sn-1 + Q sn-2 and are also known as Horadam Sequences H( s0, s1, P, Q ) after Alwyn Horadam who wrote about them in 1965.
sn = P sn-1 + Q sn-2
PQs0s1s2 ... nameGenerating FnOEIS
11 011,2,3,5,8... Fibonacci F(n)
x
1 – x – x2
A000045
101,1,2,3,5,8... Fibonacci F(n-1)
1 – x
1 – x – x2
A000045
213,4,7,11,18,... Lucas L(n)
2 – x
1 – x – x2
A000032
F(0)+F(k)F(1)+F(k+1)... F(n) + F(n+k)
F(k+1) + (F(k-1) + 1) x
1 – x – x2
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:
aba+b,a+2b,2a+3b,... Generalised Fibonacci
G(a,b,n) = F(n-1) a + F(n) b
a + (b – a) x
1 – x – x2
G(a,b)
-11 01-1,2,-3,5,-8... Fibonacci( – n )
x
1 + x – x2
A039834
101,-1,2,-3,5,-8... F( 1 – n )
1 + x
1 + x – x2
aba-b,-a+2b,2a-3b,-3a+5b,... F( 1 – n ) a + F( –n ) b
a + ( a+b ) x
1 + x – x2
12 011,3,5,11,21... Jacobsthal J(n)
x
1 – x – 2 x2
A001045
102,2,6,10,22,42... 2 J(n-1)
1 – x
1 – x – 2 x2
A078008
215,7,17,31... Jacobsthal-Lucas
2 – x
1 – x – 2 x2
A014551
ab2a+b,2a+3b,6a+5b,10a+11b,...
a + (b – a) x
1 – x – 2 x2
21 012,5,12,29... Pell
Denominators of CF convergents to √2
x
1 – 2 x – x2
A000129
113,7,17... Numerators of CF convergents to √2
1 – x
1 – 2 x – x2
A001333
101,2,5,12,29... Pell(n-1)
1 – 2 x
1 – 2 x – x2
A000129
226,14,34... Companion Pell, Pell-Lucas
2 – 2 x
1 – 2 x – x2
A002203
aba+2b,2a+5b,5a+12b,.. Pell(n) a + Pell(n+1) b
a + (b – 2 a) x
1 – 2 x – x2
2-1 012,3,4,5... the whole numbers
x
1 – 2 x + x2
A000027
10-1,-2,-3,-4,-5... the negative numbers
– x
1 – 2 x + x2
A001478
024,6,8... the even numbers
2 x
1 – 2 x + x2
A005843
036,9,12,15... 3n
the sum of 3 consecutive integers
3
1 – 2 x + x2
A008585
135,7,9... the odd numbers
1 + x
1 – 2 x + x2
A005408
2610,14,18,22.. 4n+2
Numbers not the side of any primitive Pythagorean triangle
the sum of 4 consecutive numbers
10 – 6 x
1 – 2 x + x2
A016825
ab2b-a,3b-2a,4b-3a... n b - (n-1)a
a + (b – 2a) x
1 – 2 x + x2
31 013,10,33,109... Ratios of terms are CF convergents to (3+√13)/2
x
1 – 3 x – x2
A006190
101,3,10,33,109... ...ditto...
1 – 3 x
1 – 3 x – x2
A006190
3-1 013,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 – 3 x + x2
A001906
10-1,-3,-8,-21,... F(2 – 2n ) = – F( 2 n – 2 )
1 – 3x
1 – 3 x + x2
125,13,34,89... F(2n+1) = F(n)2 + F(n+1)2
1 – x
1 – 3 x + x2
A001519
51025,65,170,... L(n)2 + L(n+1)2
= 5 F(2n+1) = 5 F(n)2 + 5 F(n+1)2
5 – 5x
1 – 3 x + x2
A106729
237,18,47,123... L(2n)
2 – 3 x
1 – 3 x + x2
A005278
1411,29,76,199... L(2n+1)
1 + x
1 – 3 x + x2
A002878
ab3b-a,8b-3a,21b-8a... F(2n) b – F(2n –2) a
a + (b–3a) x
1 – 3 x + x2
3-2 013,7,15,31,63... 2n – 1
x
1 – 3 x + 2 x2
A000225
235,9,17,33,65... 2n + 1
2 – 3 x
1 – 3 x + 2 x2
A000051
ab3b-2a,7b-6a,15b-14a... (2n - 1) b - (2n - 2) a
a + (b – 3a) x
1 – 3 x + 2 x2
41 0 1 4,17,72... Denominators of CF convergents to √5
=Fib(3n)/2
x
1 – 4 x – x2
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 – x2
A001077
F(0)=0F(3)=28,34,144... F(3n)
2 x
1 – 4 x – x2
A014445
F(1)=1F(4)=313,55... F(3n+1)
1 – x
1 – 4 x – x2
A033887
F(2)=1F(5)=521,89... F(3n+2)
1 + x
1 – 4 x – x2
A015448
aba+4b,4a+17b,17a+72b... ( F(3n) a + F(3n+3) b )/2
a + (b – 4a) x
1 – 4 x – x2
6 -1 016,35,204... Numbers n such that n2 is a Triangular number
= Pell(2n)/2
x
1 – 6 x + x2
A001109
0212,70,408... Pell(2n), the even Pell numbers
2 x
1 – 6 x + x2
A001542
1529,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 + x2
A001653
ab-a+6b,-6a+35b,-35a+204b...
a + (-6a+b) x
1 – 6 x + x2
7 -1 017,48,329... F(4n)/3
x
1 – 7 x + x2
A004187
ab7b-a,48b-7a,...
F(4n) b – F(4n-4) a
3
a + (b – 7a) x
1 – 7 x + x2

sn = P sn-1 + Q sn-2
PQs0s1nameGen. 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)kx2
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)kx2
ab
a + ( b – a L(k) ) x
1 – L(k) x – (-1)kx2
n 1 01
Denominators of CF convergents of  n + √(n2+4)
2

whose CF is [n; n,n,n,n,...]
x
1 – n x – x2
1n Numerators of CF convergents of
CF [n; n,n,n,n,...]
1
1 – n x – x2
PQ ab General second order recurrence
a – (a P - b) x
1 – P x – Q x2

Order 3

sn = P sn-1 + Q sn-2 + R sn-3
PQRs0s1s2 s3 ...nameGen. Fn.OEIS
0110010,1,1,1,2,2,3,4,5,7... Padovan
x2
1 – x2 – x3
A000931
0210112,3,5,8,13... Fibonacci
F(n+3)=2F(n+1)+F(n)
Vajda-8 with m=3)
x (1 + x)
(1 – x – x2) (1 + x)
A000045
1110011,2,4,7,13,24... Tribonacci numbers
x2
1 – x – x2 – x3
A000073
20-10112,3,5,8,13... Fibonacci
B&Q(2003) Identity 16
x (1 – x)
(1 – x – x2 )( 1 – x )
A000045
22 -1 0114,9,25,64... F(n)2
x – x2
1 – 2 x – 2 x2 + x3
=
x ( 1 – x )
( 1 + x )( 1 – 3 x + x2)
A007598
0126,15,... F(n)F(n+1)=(F(n+2)2-F(n-1)2)/4
x
1 – 2 x – 2 x2 + x3
A001654
02310,24,... F(n)F(n+2)
2 x – x2
1 – 2 x – 2 x2 + x3
A059929
03516,39,... F(n-1)F(n+2)=F(n+1)2-F(n)2
3 x – x2
1 – 2 x – 2 x2 + x3
A226205
04824,60,160,... F(n+3)2 – F(n)2
= 4 F(n) F(n+1)
4 x
1 – 2 x – 2 x2 + x3
A192883
05826,63,... F(n-2)F(n+2)
5 x – 2 x2
1 – 2 x – 2 x2 + x3
A192883
382563,168... F(n+5)2-F(n)2
3 + 2x + 3x2
1 – 2 x – 2 x2 + x3
41916,49,121... L(n)2
4 – 7 x – x2
1 – 2 x – 2 x2 + x3
A001254
231228,77,198... L(n)L(n+1)
2 – x + 2 x2
1 – 2 x – 2 x2 + x3
A215602
abc-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 ) x2
1 – 2 x – 2 x2 + x3
0ab2a+2b, 3a+6b, 10a+15b, ... F(n)G(a,b,n-1)
a x + ( b – 2 a )x2
1 – 2 x – 2 x2 + x3
a2b2(a+b)2(a+2b)2, (2a+3b)2 ... G(a,b,n)2
a2 + (b2 – 2 a2) x – (a – b)2 x2
1 – 2 x – 2 x2 + x3
abb(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) x2
1 – 2 x – 2 x2 + x3
3-31 0123,4,5... Natural Numbers
x ( x – 1)
(x – 1)2(x – 1)
A000217
0136,10,15... Triangular Numbers = n ( n + 1 ) / 2
x
(x – 1)3
A000217
0149,16,25... Square Numbers = n2
x (x + 1)
(x – 1)3
A000290
01512,22,35... Pentagonal Numbers
=n ( 3 n – 1) / 2
x (2 x + 1)
(x – 1)3
A000326
01N3N-3,6N-8,10N-15,... Polygonal Numbers
Figurate Numbers
with N sides= n [ N (n-1) /2 - (n-2) ]
x + (N-3) x2
(x – 1)3
Mathworld:Figurate Numbers
151325,41,61, ... Hypotenuses h of Pythagorean
triangles with sides (a, h-1, h)
= 4 Triangular(n) + 1
= 2 n2 + 2 n + 1
(1 + x) 2
(x – 1)3
A001844
7-71 0320119,696,... Smallest leg,a, of Pythagorean
triangles (a,a+1,h)
3 – x
1 – 7 x + 7 x2 – x3
A001652
8-8-1 01964,441... F(2n)2
x + x2
1 – 8 x + 8 x2 – x3
=
x ( 1 + x )
( 1 – x )( 1 – 7 x + x2 )
A049684
122252 169...F(2n+1)2
1 – 4 x + x2
1 – 8 x + 8 x2 – x3
A081068
1717-1 022821156... F(3n)2
4 x – 4 x2
– 1 + 17 x + 17 x2 – x3
=
4 (x – 1) x
( 1 + x )( 1 – 18 x + x2 )
A014729
12321323025... F(3n+1)2
– 1 + 8 x + x2
– 1 + 17 x + 17 x2 – x3
12522127921... F(3n+2)2
– 1 – 8 x + x2
– 1 + 17 x + 17 x2 – x3

sn = P sn-1 + Q sn-2 + R sn-3
PQRs0s1s2seriesGen.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 ) x2
(x + (-1)k)(x2 – L(2k) x + 1)
for i in {0..k-1}
PQRabc General Third order Recurrence
a – ( a P - b) x – ( a Q + b P - c ) x2
1 - P x - Q x2 - R x3

Order 4

sn = P sn-1 + Q sn-2 + R sn-3 + S sn-4
PQRSs0s1s2s3seriesname
36-3-1 01188,27,125... F(n)3
1 – 2x – x2
1 – 3 x – 6 x2 + 3 x3 + x4
=
1 – 2x – x2
( x2 – x – 1 )( x2 + 4 x – 1 )
A056570
00013,15,60,260 F(n-1)F(n)F(n+1)/2
1
1 – 3 x – 6 x2 + 3 x3 + x4
A001655
00026,30,120,520 F(n-1)F(n)F(n+1)
2
1 – 3 x – 6 x2 + 3 x3 + x4
A065563
001212,45,200... F(n)2F(n+1)
x – x2
1 – 3 x – 6 x2 + 3 x3 + x4
A066258
0031048,195,840... F(n-1)F(n)F(n+2)
3 x + x2
1 – 3 x – 6 x2 + 3 x3 + x4
A220362
0201024,130,504... F(n-2)F(n)F(n+2)
2 – 6 x – 2 x2
1 – 3 x – 6 x2 + 3 x3 + x4
A226958
1061580,312,1365... F(n-2)F(n)F(n+1)
x – 3 x2
1 – 3 x – 6 x2 + 3 x3 + x4
A220360
0-35039,105,544 F(n-2)F(n)F(n+3)
3 – 9 x – 2 x2
1 – 3 x – 6 x2 + 3 x3 + x4
112935,152... F(n)3+F(n+1)3
1 – x – 3 x2 – 3 x3
1 – 3 x – 6 x2 + 3 x3 + x4
A110224
1928133539,2322.. F(n)3+F(n+2)3
1 + 6 x – 5 x2 – 2 x3
1 – 3 x – 6 x2 + 3 x3 + x4
A226976
F(n)3+F(n+k)3
(1 – 2x – x2)(1 + xk)
1 – 3 x – 6 x2 + 3 x3 + x4
F(n)F(n+a)F(n+b)
(-1)b( F(a+1)F(b+1) x + G(-L(b),F(b-2),a) x2 – F(b-1)F(a-1) x3 )
1 – 3 x – 6 x2 + 3 x3 + x4
N J SLoane has a list of links into OEIS for linear recurrences: Index entries for sequences related to linear recurrences with constant coefficients

Generating Functions

Ordinary Generating Functions

For many series, S(n), we can find a (simple) power-series expression in x (that is, a sum of powers of x) where the coefficients of the nth power of x is the nth term in the series, S(n):
G(x) =
Σ
i=0
 S(i) xi  = S(0) + S(1) x + S(2) x2 + S(3) x3 + ...
Such an expression, G(x), if it exists for the series S is called the generating function for S or GF for short.

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 – x2
| Lucas(n)
2,1,3,4,7,...
2 – x
1 – x – x2
| G(a,b,n)
a,b,a+b,a+2b,...
a + (b – a) x
1 – x – x2
Fibonacci(2n)
0,1,3,8,21,...
x
x2 – 3 x + 1
Lucas(2n)
2,3,7,18,...
2 – 3 x
x2 – 3 x + 1
G(a,b,2n)
a,a+b,2a+3b,...
a + (b – 2a) x
x2 – 3 x + 1
Fibonacci(2n+1)
1,2,5,13,...
1 – x
x2 – 3 x + 1
Lucas(2n+1)
1,4,11,29,...
1 + x
x2 – 3 x + 1
G(a,b,2n+1)
b,a+2b,3a+5b,...
b + (a – b) x
x2 – 3 x + 1
Fibonacci(3n)
2,8,34,144,...
2 x
1 – 4 x – x2
Lucas(3n)
2,4,18,76,...
2 – 4 x
1 – 4 x – x2
G(a,b,3n)
a,a+2b,5a+8b,...
a + (2 b – 3 a) x
1 – 4 x – x2
Fibonacci(3n+1)
1,3,13,55,...
3 + x
1 – 4 x – x2
Lucas(3n+1)
3,11,47,199,...
3 x + 1
1 – 4 x – x2
G(a,b,3n+1)
a+b,3a+5b,13a+21b,...
b + (2 a – b) x
1 – 4 x – x2
Fibonacci(3n+2)
1,5,21,89,...
x + 1
1 – 4 x – x2
Lucas(3n+2)
2,4,18,76,...
3 – x
1 – 4 x – x2
G(a,b,3n+2)
a,a+2b,5a+8b,...
a + b + (b – a) x
1 – 4 x – x2
Fibonacci(k n)
F(k) x
1 – L(k) x + (–1)k x2
Lucas(k n)
2 – L(k) x
1 – L(k) x + (–1)k x2
G(a,b,kn)
a+(F(k)b–F(k+1)a)x
1–L(k)x+(–1)kx2
Fibonacci(n)2
02,12,12,22,32,...
x – x2
1 – 2 x – 2 x2 + x3
Lucas(n)2
22,12,32,42,...
4 – 7 x – x2
1 – 2 x – 2 x2 + x3
G(a,b,n)2
a2,b2,(a+b)2,...
a2+(b2–2a2)x–(a–b)2x2
1–2x–2x2+x3
Fib(n)Fib(n+1)
1×1,1×2,2×3,3×5,...
x
1 – 2 x – 2 x2 + x3
Lucas(n)Lucas(n+1)
2×1,1×3,3×4,4×7,...
2 – x + 2 x2
1 – 2 x – 2 x2 + x3
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)x2
1–2x–2x2+x3
Fibonacci(n)3
03,13,13,23,33,...
x–2x2–x3
1–3x–6x2+3x3+x4
Lucas(n)3
23,13,33,43,...
8–23x–24x2+x3
1–3x–6x2+3x3+x4
Replacing x by x2 in a GF inserts 0's between all values of the original series.
The series of even-indexed Fibonacci numbers only is the series 0,1,1,2,3,5,8,...
so it has the same GF as Fibonacci(2n) but with x2 replacing x: x2/(x4 – 3 x2 + 1) for the series 0,0,1,0,3,0,8,0,21,... .

The GF of 1,2,5,13,... is that of Fib(2n+1) which is (1 – x)/(x2 – 3 x + 1)
so 1,0,2,0,5,0,13,... has GF (1 – x2)/(x4 – 3 x2 + 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 x2n+1 is therefore x (1 – x2)/(x4 - 3 x2 + 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 x2n and Fib(2n+1) as the coefficient of x2n+1 should then give the complete Fibonacci series GF:

0,0,1,0,3,0,8, 0,21, ... +
0,1,0,2,0,5,0,13, 0, ...
0,1,1,2,3,5,8,13,21,...
We can check that x2/(x4 - 3 x2 + 1) + x (1 – x2)/(x4 - 3 x2 + 1) = x/(1 – x – x2)
which is the GF of 0,1,1,2,3,5,8,13,21,... as required!

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.
Check that a Fib[n-1] + b Fib[n] gives the GF of G(a,b).

Exponential Generating Functions

Sum
n
F(n)
zn   =   ePhi z - e -phi z
n!√5
, z in C
See, e.g., Solving Linear Recurrences from Differential Equations
in the Exponential Manner and Vice Versa
W Oberschelp
in Applications of Fibonacci Numbers Vol 6 (1996) pages 365-380

Trigonometric Formulae

F(n) =
floor( (n-1)/2 )
Product
k = 1
( 3 + 2 cos  2kπ )
--
n
, n ≥ 1
D Lind, Problem H-93, FQ 4 (1966), page 332
L(n) =
floor( (n-2)/2 )
Product
k = 0
( 3 + 2 cos  (2k+1)π )
--
n
, n ≥ 2
D Lind, Problem H-93, FQ 4 (1966), page 252, corrected page 332

Hyperbolic Functions

Here we use g for ln(Phi), the natural log of Phi so that cosh(g) = √5 / 2.
Several of the formulae above can be derived using hyperbolic functions - see chapter XI of Vajda.
F( 2n ) = 2sinh( 2ng )
--
√5
from Binet's formula
         =  sinh( 2ng )
--
cosh( g )
F( 2n+1 ) = 2cosh( (2n+1)g )
--
√5
from Binet's formula
         =  cosh( (2n+1)g )
--
cosh( g )
L( 2n) = 2 cosh( ng )from Binet's formula
L( 2n+1 ) = 2 sinh( ng )from Binet's formula

Complex Numbers

Here i is √–1
F(n) =
n–1
Product
k = 1
( 1 – 2 i cos  k π )
--
n
D Lind, Problem H-64, FQ 3 (1965), page 116
F(n) = 2 i–n sin(–i n ln( i Phi) )
--
√5
from Rabinowitz-7 corrected
F(n) = 2 i–n sinh(n ln( i Phi) )
--
√5
from Rabinowitz-7 corrected
L(n) = 2 i–n cos(–i n ln( i Phi) ) from Rabinowitz-7 corrected
L(n) = 2 i–n cosh( n ln( i Phi) ) from Rabinowitz-7 corrected
1 + 2i = √Phi+i/√Phi = [1+i, 2+2i] I J Good (1993)
2 √1 + i/2 = (1 + i) √Phi + (1 – i) √phi I J Good (1993)

References

(*) above indicates a private communication.
Book: : a book;
Article: : an article (chapter) in a journal (book);
WWW: : a web resource.
FQ : The Fibonacci Quarterly journal
Arranged in alphabetical order of author:

Book: A T Benjamin, J J Quinn Proofs That Really Count Mathematical Association of America, 2003, ISBN 0-88385-333-7, hardback, 194 pages. shown as B&Q(2003) in the Table above
Art Benjamin and Jennifer Quinn have a wonderful knack of presenting proofs that involve counting arrangements of dominoes and tiling patterns in two ways that convince you that a formula really is true and not just "proved"! The identities proved mainly involve Fibonacci, Lucas and the General Fibonacci series with chapters on continued fractions, binomial identites, the Harmonic and Stirling numbers too. There is so much here to inspire students to find proofs for themselves and to show that proofs can be fun too!
Important notation difference: Benjamin and Quinn use fn for the Fibonacci number F(n+1)
Article: Bergum and Hoggatt (1975)
G. E. Bergum and V. E. Hoggatt, Jr. Sums and Products for Recurring Sequences, Fib Q 13 (1975), pages 115-120.
Article: Benjamin, Carnes, Cloitre (2009)
Recounting the Sums of Cubes of Fibonacci Numbers A T Benjamin, T A. Carnes, B Cloitre, Congressus Numerantium, Proceedings of the Eleventh International Conference on Fibonacci Numbers and their Applications, William Webb (ed.), Vol 194, pp. 45-51, 2009.
Book: L E Dickson History of the Theory of Numbers: Vol 1 Divisibility and Primality
is a classic and monumental reference work on all aspects of Number Theory in 3 volumes (volume II is on Diophantine Analysis and volume III on Quadratic and Higher Forms). Although not up-to-date (the original edition was 1952) it is still a comprehensive summary of useful historical and early references on all aspects of Number Theory. The link is to a new cheap Dover paperback edition (2005) of Volume 1 which contains the most about Fibonacci Numbers, Lucas numbers and the golden section: see Chapter XV11 on Recurring Series, Lucas' un, vn where he uses the series of Pisano for what we now call the Fibonacci numbers.
Book: R A Dunlap, The Golden Ratio and Fibonacci Numbers World Scientific Press, 1997, 162 pages.
An introductory book strong on the geometry and natural aspects of the golden section but it does not include much on the mathematical detail. Beware - some of the formulae in the Appendix are wrong! Dunlap has copied them from Vajda's book (see below) and he has faithfully preserved all of the original errors! The formulae on this page (that you are now reading) are corrected versions and have been verified.
Article:Fairgrieve and Gould (2005)
Product Difference Fibonacci Identities of Simson, Gelin-Cesáro, Tagiuri and Generalizations. S Fairgrieve and H W Gould, The Fibonacci Quarterly 43 (2005), 137-141.
Article:Gould (1977)
H W Gould, A Fibonacci Formula of Lucas and its Subsequent Manifestations and Rediscoveries , Fibonacci Quarterly vol 15 (1977) pages 25-29
Book: R L Graham, D E Knuth, O Patashnik Concrete Mathematics Second Edition (1994), hardback, Addison-Wesley.
No - this is not a book about proportions of sand to cement when laying foundations for buildings :-). The title is meant as an antidote to the "Abstract Mathematics" courses so often found in the curricullum of a university maths degree.
As such, it is the book to dip into if you want to go really deeply into any part of the mathematics covered on this Fibonacci and Phi site. However, it quickly gets to an advanced mathematics undergraduate level after some nice introductions to every topic.
There are notes left in the margins which were inserted by students taking the original courses based on this book at Stanford university and they are interesting, often useful and sometimes quite funny.
Book: V E Hoggatt Jr "Fibonacci and Lucas Numbers" published by The Fibonacci Association, 1969 (Houghton Mifflin).
A very good introduction to the Fibonacci and Lucas Numbers written by a founder of the Fibonacci Quarterly.
Article: Hoggatt and Lind (1969)
V E Hoggatt Jr, D A Lind, Compositions and Fibonacci Numbers, The Fibonacci Quarterly, Vol. 7, No. 3 (Oct., 1969), pp. 253-266.
Article: F T Howard (2003) "The Sum of the Squares of Two Generalized Fibonacci Numbers" FQ vol 41 pages 80-84.
Article: Hudson and Winans (1981)
A Complete Characterization of the Decimal Fractions That Can Be Represented as Σ 10k(a + 1)Fai , where Fai is the aith Fibonacci Number R H Hudson, C F Winans The Fibonacci Quarterly 19, no. 5 (1981) pages 414-421.
See also:
A Complete Characterization Of B-Power Fractions That Can Be Represented As Series Of General N-Bonacci Numbers J-Z Lee, J-S Lee Fibonacci Quarterly 25 (1987) pages 72-75.
Article: I J Good Complex Fibonacci And Lucas Numbers, Continued Fractions, And The Square Root Of The Golden Ratio, Fib Q 31 (1993) pages 7-19
WWW: R Johnson (Durham university) has an excellent web page
on the power of matrix methods to establish many Fibonacci formula with ease (but it does rely on at least undergraduate level matrix mathematics). See the Matrix methods for Fibonacci and Related Sequences link to a Postscript and PDF version on his Fibonacci Resources web page.
The latest version (Nov 12, 2004) contains an appendix showing how formulae developed in Johnson's paper can prove almost all the identities here in my table above.
Book: D E Knuth The Art of Computer Programming: Vol 1 Fundamental Algorithms hardback, Addison-Wesley third edition (1997).
The paperback is now out of print and hard to find. This is the first of three volumes and an absolute must for all computer scientist/mathematicians.
Book: T Koshy Fibonacci and Lucas Numbers with Applications, Wiley-Interscience, 2001, 648 pages.
This is a new book packed full of an amazing number of Fibonacci and related equations, culled from the pages of the Fibonacci Quarterly. Although initially impressive in its size and breadth, be aware that there are far too many typos, errors and missing or irrelevant conditions in many of its formulae as well as some glaring omissions and misattributions particularly with respect to the original references for a number of the formulae. Although Fibonacci representations of integers are included Zeckendorf himself is never even mentioned! There are lots of exercises with answers to the odd-numbered questions.
Article: Long (1981)
The Decimal Expansion Of 1/89 And Related Results C Long Fibonacci Quarterly 19 (1985) pages 53-55
Article: E Lucas, "Théorie des Fonctions Numériques Simplement Périodiques" in American Journal of Mathematics vol 1 (1878) pages 184-240 and 289-321.
Reprinted as The Theory of Simply Periodic Functions, the Fibonacci Association, 1969.
Article: R S Melham (1999) "Families of Identities Involving Sums of Powers of the Fibonacci and Lucas Numbers" FQ vol 37, pages 315-319.
Article: R S Melham (2011), On Product Difference Fibonacci Identities Article A10, Integers, vol 11
Article: Ohtsuka and Nakamura (2010)
A New Formula For The Sum Of The Sixth Powers Of Fibonacci Numbers H Ohtsuka, S Nakamura, Congressus Numerantium Vol. 201 (2010), Proceedings of the Thirteenth Conference on Fibonacci Numbers and their Applications , pp.297-300.
Article: S Rabinowitz "Algorithmic Manipulation of Fibonacci Identities" in Applications of Fibonacci Numbers: Proceedings of the Sixth International Research Conference on Fibonacci Numbers and their Applications, editors G E Bergum, A N Philippou, A F Horodam; Kluwer Academic (1996), pages 389 - 408.
Book: S Vajda, Fibonacci and Lucas numbers, and the Golden Section: Theory and Applications, Dover Press (2008).
This is a wonderful book, a classic, originally published in 1989 and now back in print in this Dover edition. This book is full of formulae on the Fibonacci numbers and Phi and the Lucas numbers. The whole book develops the formulae step by step, proving each from earlier ones or occasionally from scratch. It has a few errors in its formulae and all of them have been dutifully and exactly copied by authors such as Dunlap (see above) and others! Where I have identified errors, they have been corrected here on this page.

Valid HTML 4.01! © 1996-2013 Dr Ron Knott email
The URL of this document is
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormulae.html
updated 16 May 2013