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.

The calculators and Contents sections on this page require JavaScript but you appear to have switched JavaScript off (it is disabled). Please go to the Preferences for this browser and enable it if you want to use the calculators, then Reload this page.

Contents of this page

The

icon means there is a You Do The Maths... section of questions to start your own investigations.

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.

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

a derangement or
a complete permutation or
a permutation without a fixed point
the subfactorial written using the upside-down exclamation mark ¡ after the number or else using the ordinary exclamation mark (as for factorial) but before the number: n¡ or !n .

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

the first seat is occupied by person `2` (who was originally sitting in seat `2`)
the second seat has the person originally in seat `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 she sits in seat `1`, then two people have been seated, `1` is in seat `i` and `i` in seat `1`, neither in their original seat. We are left with `n-2` people in `n-2` seats -- the same problem but with `2` less people
On the other hand, if she does not sit in seat `1`, then we relabel seat `1` as "`i`" (she is not going to sit there) and there are `n-1` people to sit in `n-1` seats, each with `1` seat forbidden to them - the same problem but with `n-1` people and 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)	1	2	3	4	5	6	...
#derangements	0	1	2	9	44	265	...

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`

You Do The Maths...

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?
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?
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:

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

You Do The Maths...

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

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

Try to find recurrence relations to describe your numbers or explicit formulae.

# 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

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:

`s_n=1` for all `n`, an order 0 recurrence
`s_n=s_(n-1), s_0=1`, an order 1 homogeneous recurrence
`s_n=2 s_(n-1)-1, s_0=1`, an order 1 non-homogeneous recurrence
`s_n=2 s_(n-1) - s_(n-2), s_0=1,s_1=1`, an order 2 homogenous recurrence
...

Usually, the recurrence of smallest order is the one most often quoted and used.

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.

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!

A Recurrence Relations Table

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

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

)

r! (n - r)!

_nC_r
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 ...

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	...

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:

0 and 1 to get the Fibonacci sequence
2 and 1 to get the Lucas numbers
a and b to get the General Fibonacci series

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 s_n is s_n-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:

Fibonacci: `s_n = s_n + s_(n-1)` is linear or order 2
`s_n = 2 s_n - s_(n-1)` is linear of order 2
`s_n = 2 s_(n-1)` is linear of order 1
`s_n = s_(n-2) + s_(n-3)` is linear of order 3
`s_n = s_(n-1) s_(n-2)` is not linear
`s_n = s_(n-1)^2` is not linear
`s_n = s_(n-1) + 1` is linear but not homogeneous because the last term, 1, does not involve an earlier term of the sequence
`s_n = n s_(n-1)` starting from `s_1=1` defines the factorial numbers as a linear recurrence (of order 1) but the coefficients are not constant.

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

`s_n = n`: an equation, not a recurrence, since the definition does not depend upon earlier terms
`s_n = s_(n-1) + 1 if n>1 and s_0=0`: an inhomogenous linear recurrence of order 1
`s_n = 2 s_(n-1) - s_(n-2) if n>2 and s_0 =0, s_1 = 1` is a linear homogeneous recurrence relation with constant coefficients

Linear homogenous recurrence relations with constant coefficients
...have the property that

if the initial terms have a common factor g then so do all the terms in the series
there is an easy method of producing a formula for s_n in terms of n.
For a given linear recurrence, the k series with initial conditions
- 1,0,0,...,0
- 0,1,0,0...,0
- ...
- 0,0,..0,1
each with k terms, may be called the spanning series for a linear recurrence or order k.
This means that they will be enough to define any other recurrence with the same linear relation by taking multiples of each according to their respective starting terms, and adding them. A formula for each of the spanning series will therefore give a formula for a series with any given initial terms.
In the table below you will find the spanning series for many of the recurrences.

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

Order 1

We include some non-homogenous recurrences here for the sake of completeness.

`s_n = P s_(n-1) + Q`
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

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)`
`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)`
-1	1	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
3	1	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)² + L(n+1)² = 5 F(2n+1) = 5 F(n)² + 5F(n+1)²	`(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 n² 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
7	-1	a	b	7b-a,48b-7a,...	`(F(4n) b - F(4n-4) a )/(3)`	`(a + (b - 7a) x)/(1 - 7 x + x^2)`

s_n = `P s_(n-1) + Q s_(n-2)`
P	Q	s₀	s₁	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)`
n	1	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)`

Order 3

s_n = P s_n-1 + Q s_n-2 + R s_n-3
P	Q	R	s₀	s₁	s₂	s₃ ...	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)²	`( 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)²	`( 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)`
			a²	b²	(a+b)²	(a+2b)², (2a+3b)² ...	G(a,b,n)²	`( 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) =F_n-1F_na² + (F_nF_n+1+F_n-1²)ab +F_nF_n+1b²	`( 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 = n²	`( 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 + 3n²	`( 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
7	-7	1	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)²	`( x + x^2)/(1 - 8 x + 8 x^2 - x^3)` `=( x ( 1 + x ))/(( 1 - x )( 1 - 7 x + x^2 ))`	A049684
8	-8	-1	1²	2²	5²	169...	F(2n+1)²	`(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
15	-15	1	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	2²	8²	1156...	F(3n)²	`( 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
			1²	3²	13²	3025...	F(3n+1)²	`( - 1 + 8 x + x^2)/(- 1 + 17 x + 17 x^2 - x^3)`
			1²	5²	21²	7921...	F(3n+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

s_n = P s_n-1 + Q s_n-2 + R s_n-3
P	Q	R	s₀	s₁	s₂	series	Gen.Fn.
L(2k)+(-1)^k	-L(2k)-(-1)^k	(-1)^k	F(i)² = a	F(k+i)² = b	F(2k+i)² = c	F(kn+i)²	`( 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)`

Order 4

s_n = P s_n-1 + Q s_n-2 + R s_n-3 + S s_n-4
P	Q	R	S	s₀	s₁	s₂	s₃	series	name	Gen. Fn.	OEIS
3	6	-3	-1	0	1	1	8	8,27,125...	F(n)³	`( 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)²F(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)³+F(n+1)³	`(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)³+F(n+2)³	`(1 + 6 x - 5 x^2 - 2 x^3 )/(1 - 3 x - 6 x^2 + 3 x^3 + x^4)`	A226976
									F(n)³+F(n+k)³	`((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

A Table of 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 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)² `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)³ `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)`.

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

Fibonacci Home Page Fibonacci and Phi Formulae

The URL of this document is https://r-knott.surrey.ac.uk/Fibonacci/LRGF.html