Processing math: 0%

Recurrence Relations & Generating Functions

This page is an extension to my Fibonacci and Phi Formulae with an introduction to Recurrence Relations and to Generating Functions.
A recurrence relation is a way of defining a series in terms of earlier member of the series. With a few initial terms, it is a complete description and if often much simpler than an explicite formula for the n-th term of the series which only uses n, not earlier terms.
A generating function (GF) is an infinite polynomial in powers of x where the n-th term of a series appears as the coefficient of x^(n) in the GF. Where there is a simple expression for the generating function, for example 1/(1-x), we can use familiar mathematical operations such as accumulating sums or differentiation and integration to find other related series and deduce their properties from the GF.
Contents of this page
The You Do The Maths... icon means there is a You Do The Maths... section of questions to start your own investigations.

1 Introduction to Recurrence Relations

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 where Phi = (sqrt5+1)/2 and phi=(sqrt5-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.

1.1 Some Examples

1.1.1 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 has n-2 choices and so on until the last person has just 1 choice. So in total there are
nxx(n-1)xx(n-2)xx...xx3xx2xx1 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 and so includes the case of most people in their original seats but some people in a new seat.
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 (who was 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. By the recurrence formula above we have
D(3) = 2 ( D(2)+D(1) ) = 2(1+0) = 2, that shows that we have 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!(1/(2!) - 1/(3!) + 1/(4!) - ... (-1)^n/(n!) ), if 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

1.1.2/ You Do The Maths... /

  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 recursive formula - that is, how many initial terms are needed to completely determine 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?

1.1.3 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!

1.1.4/ You Do The Maths... /

  1. In our derangements, all n items get moved to a different place.
    But given a permutation of n items, we can count how many of them remain fixed and how many items move.
    Take the 4xx3xx2=24 permutations of {1,2,3,4}. Count how many items in each permutation are fixed (it will be 0,1,2,3 or 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.

1.2 Recurrence Types and Properties

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 4^(th) term before each 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) = 2 s(n-1) + 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.
Note also that the recurrence for a series is not unique.
For instance the Fibonacci numbers are F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) which gives the series starting at 0. Any series can have a different initial term, so here we can have F(0)=1, F(1)=1, F(n)=F(n-1)+F(n-1).
More importantly, there can be recurrence relations of different orders for the same series with the same initial terms.
For instance, the series 1,1,1,1,1,... is described by all these forms of recurrences: Usually, the recurrence of smallest order is the one most often quoted and used.

2 Introduction to Generating Functions

Many series have a very compact representation as the coefficients of a power series:
the series s_0, s_1, s_2, ... , s_n, ... are the coefficients of x^0, x^1, x^2, ... , x^n, ... . 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) = 1+x+x^2+x^3+... so we say that the series (of coefficients) 1,1,1,1,1,... has generating function 1/(1-x).
1/((1-x)^2) = 1 + 2 x + 3 x^2 + 4 x^3 + ... 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.

2.1 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 + x^2)
and it has the recurrence
s_n = 2 s_(n-1) - s_(n-2)
We can see the relationship more clearly if we rewrite the recurrence in this form:
s_n - 2 s_(n-1) + s_(n-2) = 0
and compare that with the denominator of the GF, namely:
1-2 x + x^2
This is a general principle!

3 A Recurrence Relations Table

3.1 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
Φ
τ τφ, α (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]
[ 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 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-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...

3.2 Linear Recurrence Relations

Linear homogeneous recurrence relations with constant coefficients and their sequences.
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 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


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

3.2.1 Order 1

We include some non-homogenous recurrences here for the sake of completeness.
s_n = P s_(n-1) + Q
PQs_0s_1, s_2, ... nameGenerating FnOEIS
10kk,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
...
-101-1,1,-1,1,-1,...(-1)^n,... The Alternating Series of 1's 1/(1+x) A033999
1daa+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
...
r0aa r, a r^2, a r^3,..., a r^n, ...Geometric Seriesa/(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

3.2.2 Order 2

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

sn = P s_(n-1) + Q s_(n-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)^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)
ab (a + ( b - a L(k) ) x)/(1 - L(k) x - (-1)^k x^2)
n 1 01 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)
1n Numerators of CF convergents of
CF [n; n,n,n,n,...]
( 1 )/(1 - n x - x^2)
PQ ab General second order recurrence ( a - (a P - b) x )/(1 - P x - Q x^2)

3.2.3 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 ( x^2)/(1 - x^2 - x^3) A000931
0210112,3,5,8,13... Fibonacci
F(n+3)=2F(n+1)+F(n)
Vajda-8 with m=3)
(x )/((1 - x - x^2) ) A000045
1110011,2,4,7,13,24... Tribonacci numbers ( x^2)/(1 - x - x^2 - x^3) A000073
20-10112,3,5,8,13... Fibonacci
B&Q(2003) Identity 16
(x )/((1 - x - x^2 )) A000045
22 -1 0114,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
0126,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
02310,24,... F(n)F(n+2) ( 2 x - x^2)/(1 - 2 x - 2 x^2 + x^3) A059929
03516,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
04824,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
05826,63,... F(n-2)F(n+2) ( 5 x - 2 x^2)/(1 - 2 x - 2 x^2 + x^3) A192883
382563,168... F(n+5)^(2)-F(n)^(2) ( 3 + 2x + 3x^2)/(1 - 2 x - 2 x^2 + x^3)
41916,49,121... L(n)2 ( 4 - 7 x - x^2)/(1 - 2 x - 2 x^2 + x^3) A001254
231228,77,198... L(n)L(n+1) ( 2 - x + 2 x^2)/(1 - 2 x - 2 x^2 + x^3) 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 ) x^2)/(1 - 2 x - 2 x^2 + x^3)
0ab2a+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)
a2b2(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)
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) x^2)/(1 - 2 x - 2 x^2 + x^3)
3-31 0123,4,5... Natural Numbers ( x )/((x - 1)^(2)) A000017
0136,10,15... Triangular Numbers = n ( n + 1 ) / 2 ( x)/((x - 1)^(3)) A000217
02612,20,30... Pronic Numbers = n ( n + 1 ) ( 2x)/((x - 1)^(3)) A002378
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
01615,28,45... Hexagonal Numbers
=n ( 2 n - 1) / 2
( x (3 x + 1))/((x - 1)^(3)) A000384
01N3N-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))
141019, 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
151325,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
161631, 51, 76, ... Centred Pentagonal Numbers
= ½ (5 n^(2) - 5 n + 2)
( 1 + 3 x + x^2)/((x - 1)^(3)) A005891
171937, 61, 91, ... Centred Hexagonal Numbers
= ½ (6 n^(2) - 6 n + 2)
= 1 - 3n + 3n2
( 1 + 4 x + x^2)/((x - 1)^(3)) A003215
11+k1+3k1+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-71 0320119,696,... Smallest leg,a, of Pythagorean
triangles (a,a+1,h)
( 3 - x)/(1 - 7 x + 7 x^2 - x^3) A001652
1849288,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 01964,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
122252 169...F(2n+1)2 (1 - 4 x + x^2)/(1 - 8 x + 8 x^2 - x^3) A081068
15-151 0112165, 2296, ... Rank of Pentagonal Numbers that are Triangular ( x (1 - 3x))/((1 - x)(1 -14x+x^2)) A046174
0120285, 3976, ... Rank of Triangular Numbers that are Pentagonal ( x (1 + 5x))/((1 - x)(1 -14x+x^2)) A046175
1717-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
12321323025... F(3n+1)2 ( - 1 + 8 x + x^2)/(- 1 + 17 x + 17 x^2 - x^3)
12522127921... F(3n+2)2 ( - 1 - 8 x + x^2)/(- 1 + 17 x + 17 x^2 - x^3)
35-351 136122541616, ... Square Triangular numbers ( 1 + x )/((1 - x )( 1 - 34 x + x^2)) A001110
195-1951 0121040755, ... Pentagonal Triangular numbers (x( 1 + 15x) )/((x - 1 )( 1 - 194 x + x^2)) A001110
9603-96031 1980194109401903638458801, ... Square Pentagonal numbers ( 1 + 198 x + x^2)/((1 - x )( 1 - 9602 x + x^2)) A036353

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 ) x^2)/((x + (-1)^(k))(x^2 - 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 ) x^2)/(1 - P x - Q x^2 - R x^3)

3.2.4 Order 4

sn = P sn-1 + Q sn-2 + R sn-3 + S sn-4
PQRSs0s1s2s3seriesname Gen. Fn.OEIS
36-3-1 01188,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
00013,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
00026,30,120,520 F(n-1)F(n)F(n+1) ( 2 )/(1 - 3 x - 6 x^2 + 3 x^3 + x^4) A065563
001212,45,200... F(n)2F(n+1) ( x - x^2 )/(1 - 3 x - 6 x^2 + 3 x^3 + x^4) A066258
0031048,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
0201024,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
1061580,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-35039,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)
112935,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
1928133539,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)
N J SLoane has a list of links into OEIS for linear recurrences: Index entries for sequences related to linear recurrences with constant coefficients

4 A Table of Generating Functions

4.1 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 n-th power of x is the n-th term in the series, S(n):
G(x) =
Σ
i=0
 S(i) x^i  = S(0) + S(1) x + S(2) x^2 + S(3) x^3 + ...
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 - 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)
Replacing x by x^2 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 Fib(2n) but with x^2 replacing x: x^2/(x^4 - 3 x^2 + 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)/(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, ... +
0,1,0,2,0,5,0,13, 0, ...
0,1,1,2,3,5,8,13,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)
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 for example for a Fib_(n-1) + b Fib_n = G(a,b).

4.2 Exponential Generating Functions

n=0
F(n) z^(n)/(n!) = (e^(\Phi z) - e^( -\varphi z) )/(\sqrt5), z \in \CC
Exponential Generating Functions For Fibonacci Identities C Church and Marjorie Bicknell, Fib Q vol 11 (1983) 275-281
n=0
L(n) z^(n)/(n!) =e^{\Phi z} + e^{ -\varphi z}, z \in bbb(C)
Exponential Generating Functions For Fibonacci Identities C Church and Marjorie Bicknell, Fib Q vol 11 (1983) 275-281

Fib HOME Fibonacci Home Page    Fibonacci and Phi Formulae

© 2013-2024 Dr Ron Knott
The URL of this document is https://r-knott.surrey.ac.uk/Fibonacci/LRGF.html
created 2013. Updated: 15 November 2024
Powered by MathJax