# Recurrence Relation

In this chapter, we will discuss how recursive techniques can derive sequences and be used for solving counting problems. The procedure for finding the terms of a sequence in a recursive manner is called **recurrence relation**. We study the theory of linear recurrence relations and their solutions. Finally, we introduce generating functions for solving recurrence relations.

Contents

## Definition

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms (Expressing F_{n} as some combination of F_{i} with i<n).

**Example** − Fibonacci series: F_{n} = F_{n−1} + F_{n−2}, Tower of Hanoi: F_{n} = 2F_{n−1} + 1

## Linear Recurrence Relations

A linear recurrence equation of degree k is a recurrence equation which is in the format x_{n} = A_{1} x_{n−1} + A_{2} x_{n−1} + A_{3} x_{n−1} +… A_{k} x_{n−k} (A_{n} is a constant and A_{k} ≠ 0) on a sequence of numbers as a first-degree polynomial.

These are some examples of linear recurrence equations −

Recurrence relations | Initial values | Solutions |
---|---|---|

F_{n} = F_{n−1} + F_{n−2} |
a_{1} = a_{2} = 1 |
Fibonacci number |

F_{n} = F_{n−1} + F_{n−2} |
a_{1} = 1, a_{2} = 3 |
Lucas number |

F_{n} = F_{n−2} + F_{n−3} |
a_{1} = a_{2} = a_{3} = 1 |
Padovan sequence |

F_{n} = 2F_{n−1} + F_{n−2} |
a_{1} = 0, a_{2} = 1 |
Pell number |

### How to solve linear recurrence relation

Suppose, a two ordered linear recurrence relation is: F_{n} = AF_{n−1} + BF_{n−2} where A and B are real numbers.

The characteristic equation for the above recurrence relation is −

x^{2} − Ax − B = 0

Three cases may occur while finding the roots −

**Case 1** − If this equation factors as (x − x_{1})(x − x_{1}) = 0 and it produces two distinct real roots x_{1} and x_{2}, then F_{n} = ax_{1}^{n}+ bx_{2}^{n} is the solution. [Here, a and b are constants]

**Case 2** − If this equation factors as (x − x_{1})^{2} = 0 and it produces single real root x_{1}, then Fn = a x_{1}^{n} + bn x_{1}^{n} is the solution.

**Case 3** − If the equation produces two distinct real roots x_{1} and x_{2} in polar form x_{1} = r ∠ θ and x_{2} = r ∠(− θ), then F_{n} = r^{n} (a cos(nθ) + b sin(nθ)) is the solution.

### Problem 1

Solve the recurrence relation F_{n} = 5F_{n−1} − 6F_{n−2} where F_{0} = 1 and F_{1} = 4

**Solution**

The characteristic equation of the recurrence relation is −

x^{2} − 5x + 6 = 0,

So, (x − 3) (x − 2) = 0

Hence, the roots are −

x_{1} = 3 and x_{2} = 2

The roots are real and distinct. So, this is in the form of case 1

Hence, the solution is −

F_{n} = ax_{1}^{n} + bx_{2}^{n}

Here, F_{n} = a3^{n} + b2^{n} (As x_{1} = 3 and x_{2} = 2)

Therefore,

1 = F_{0} = a3^{0} + b2^{0} = a+b

4 = F_{1} = a3^{1} + b2^{1} = 3a+2b

Solving these two equations, we get a = 2 and b = −1

Hence, the final solution is −

F_{n} = 2.3^{n} + (−1) . 2^{n} = 2.3^{n} − 2^{n}

### Problem 2

Solve the recurrence relation F_{n} = 10F_{n−1} − 25F_{n−2} where F_{0} = 3 and F_{1} = 17

**Solution**

The characteristic equation of the recurrence relation is −

x^{2} − 10x −25 = 0,

So, (x − 5)^{2} = 0

Hence, there is single real root x_{1} = 5

As there is single real valued root, this is in the form of case 2

Hence, the solution is −

F_{n} = ax_{1}^{n} + bnx_{1}^{n}

3 = F_{0} = a.5^{0} + b.0.5^{0} = a

17 = F_{1} = a.5^{1} + b.1.5^{1} = 5a+5b

Solving these two equations, we get a = 3 and b = 2/5

Hence, the final solution is −

F_{n} = 3.5^{n} + (2/5) .n.2^{n}

### Problem 3

Solve the recurrence relation F_{n} = 2F_{n−1} − 2F_{n−2} where F_{0} = 1 and F_{1} = 3

**Solution**

The characteristic equation of the recurrence relation is −

x^{2} −2x −2 = 0

Hence, the roots are −

x_{1} = 1 + i andx_{2} = 1 − i

In polar form,

x_{1} = r ∠ θ andx_{2} = r ∠(− θ), where r = √2 and θ = π / 4

The roots are imaginary. So, this is in the form of case 3.

Hence, the solution is −

F_{n} = (√2 )^{n} (a cos(n. π / 4) + b sin(n. π / 4))

1 = F_{0} = (√2 )^{0} (a cos(0. π / 4) + b sin(0. π / 4) ) = a

3 = F_{1} = (√2 )^{1} (a cos(1. π / 4) + b sin(1. π / 4) ) = √2 ( a/√2 + b/√2)

Solving these two equations we get a = 1 and b = 2

Hence, the final solution is −

F_{n} = (√2 )n (cos(n. π / 4) + 2 sin(n. π / 4))

## Particular Solutions

A recurrence relation is called non-homogeneous if it is in the form

*F _{n} = AF_{n−1} + BF_{n−2} + F(n)*where F(n) ≠ 0

The solution (a_{n}) of a non-homogeneous recurrence relation has two parts. First part is the solution (a_{h}) of the associated homogeneous recurrence relation and the second part is the particular solution (at). So, a_{n} = a_{h} + a_{t}.

Let F(n) = cx^{n} and x_{1} and x_{2} are the roots of the characteristic equation −

x^{2} = Ax + B which is the characteristic equation of the associated homogeneous recurrence relation −

- If x ≠ x
_{1}and x ≠ x_{2}, then a_{t}= Ax^{n} - If x = x
_{1}, x ≠ x_{2}, then a_{t}= Anx^{n} - If x = x
_{1}= x_{2}, then a_{t}= An^{2}x^{n}

### Problem

Solve the recurrence relation F_{n} = 3F_{n−1} + 10F_{n−2} + 7.5^{n} where F_{0} = 4 and F_{1} = 3

**Solution**

The characteristic equation is −

x^{2} − 3x −10 = 0

Or, (x − 5)(x + 2) = 0

Or, x_{1}= 5 and x_{2} = −2

Since, x = x_{1} and x ≠ x_{2}, the solution is −

a_{t} = Anx^{n} = An5^{n}

After putting the solution into the non-homogeneous relation, we get −

An5^{n} = 3A(n − 1)5^{n−1} + 10A(n − 2)5^{n−2} + 7.5^{n}

Dividing both sides by 5^{n−2}, we get −

An5^{2} = 3A(n − 1)5 + 10A(n − 2)5^{0} + 7.5^{2}

Or, 25An = 15An − 15A + 10An − 20A + 175

Or, 35A = 175

Or, A = 5

So, F_{n} = n5^{n+1}

Hence, the solution is −

F_{n} = n5^{n+1} + 6.(−2)^{n} −2.5^{n}

## Generating Functions

**Generating Functions** represents sequences where each term of a sequence is expressed as a coefficient of a variable *x* in a formal power series.

Mathematically, for an infinite sequence, say a_{0}, a_{1}, a_{2},…………, a_{k},………, the generating function will be −

### Some Areas of Application

Generating functions can be used for the following purposes −

- For solving a variety of counting problems. For example, the number of ways to make change for a Rs. 100 note with the notes of denominations Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 and Rs.50
- For solving recurrence relations
- For proving some of the combinatorial identities
- For finding asymptotic formulae for terms of sequences

### Problem 1

What are the generating functions for the sequences {a_{k}} with a_{k}= 2 and = 3k?

**Solution**

When a_{k} = 2, generating function,

G(x)=∑∞k=02xk=2+2x+2x2+2x3+.........G(x)=∑k=0∞2xk=2+2x+2×2+2×3+………

When ak=3k,G(x)=∑∞k=03kxk=0+3x+6x2+9x3+......ak=3k,G(x)=∑k=0∞3kxk=0+3x+6×2+9×3+……

### Problem 2

What is the generating function of the infinite series; 1, 1, 1, 1, ……….?

**Solution**

Here, a_{k} = 1, *for* 0 ≤k≤ ∞.

Hence, G(x)=1+x+x2+x3+........=1(1−x)G(x)=1+x+x2+x3+……..=1(1−x)

### Some Useful Generating Functions

- For ak=ak,G(x)=∑∞k=0akxk=1+ax+a2x2+.........=1(1−ax)ak=ak,G(x)=∑k=0∞akxk=1+ax+a2x2+………=1(1−ax)
- For ak=(k+1),G(x)=∑∞k=0(k+1)xk=1+2x+3x2.........=1(1−x)2ak=(k+1),G(x)=∑k=0∞(k+1)xk=1+2x+3×2………=1(1−x)2
- For ak=cnk,G(x)=∑∞k=0cnkxk=1+cn1x+cn2x2+.........+x2=(1+x)nak=ckn,G(x)=∑k=0∞cknxk=1+c1nx+c2nx2+………+x2=(1+x)n
- For ak=1k!,G(x)=∑∞k=0xkk!=1+x+x22!+x33!.........=exak=1k!,G(x)=∑k=0∞xkk!=1+x+x22!+x33!………=ex