Recurrence Relations · Linear Recurrence Relations

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Now we are ready to generalize this method. In a linear recurrence relation of order \(k\), \(k\) initial conditions are given: \[F(1)=f_{1}, \dotsc, F(k)=f_{k},\] as well as a linear rule such that for any \(n>k\), the value \(F(n)\) is determined by the \(k\) previous values: \[F(n)=c_{1}F(n-1)+c_{2}F(n-2)+\dotsb+c_{k}F(n-k)+g(n) \ .\] It is called homogeneous if the term \(g(n)\) is absent. The characteristic polynomial of such a relation is the following degree-\(k\) polynomial: \[P(x)=x^{k}-c_{1}x^{k-1}-c_{2}x^{k-2}-\dotsb-c_{k}.\]

Below, we will explore how to solve homogeneous linear recurrence relations of order two, followed by a generalization. The characteristic polynomial of a second-order recurrence relation has degree two and thus has two roots (which can be real or complex). Let us consider three cases with examples.

Two distinct real roots. \[F(0)=1,\quad F(1)=3,\quad F(n)=5F(n-1)+6F(n-2).\] The roots of the characteristic polynomial \(x^{2}-5x-6\) are \(-1\) and \(6\). The general solution is \(F(n)=a(-1)^{n}+b6^{n}\). Using the initial conditions \(1=a+b\) and \(3=-a+6b\), we find that \(a=3/7\) and \(b=4/7\). Thus, the solution is: \[{F(n)=\frac{3}{7}(-1)^n+\frac{4}{7}6^n}.\]
```
from sympy import Function, rsolve
from sympy.abc import n

f = Function('f')
rec = f(n) - 5 * f(n - 1) - 6 * f(n - 2)

print(rsolve(rec, f(n)))
print(rsolve(rec, f(n), {f(0): 1, f(1): 3}))
```
```
(-1)**n*C0 + 6**n*C1
3*(-1)**n/7 + 4*6**n/7
```

A real root of multiplicity two. \[F(0)=0,\quad F(1)=1,\quad F(n)=4F(n-1)-4F(n-2).\] The characteristic polynomial \(x^{2}-4x+4\) has a root \(x=2\) of multiplicity two. In this case, the general solution is a linear combination of \(2^{n}\) and \(n2^{n}\): \(F(n)=a2^{n}+bn2^{n}\). Verifying that \(n2^{n}\) satisfies the recurrence relation: \[4(n-1)2^{n-1}-4(n-2)2^{n-2}=(2n-2)2^{n}-(n-2)2^{n}=n2^{n}.\] Using the initial conditions, we find that \(a=0\) and \(b=1/2\). Thus, the solution is: \[F(n)=\frac{1}{2}n2^{n}=n2^{n-1}.\]
```
from sympy import Function, rsolve
from sympy.abc import n

f = Function('f')
rec = f(n) - 4 * f(n - 1) + 4 * f(n - 2)

print(rsolve(rec, f(n)))
print(rsolve(rec, f(n), {f(0): 0, f(1): 1}))
```
```
2**n*(C0 + C1*n)
2**n*n/2
```

Two complex roots. \[F(0)=0,\quad F(1)=1,\quad F(n)=F(n-1)-4F(n-2).\] The roots of the characteristic polynomial \(x^{2}-x+4\) are the complex numbers \((1 \pm i\sqrt{15})/2=2e^{\pm i\theta}\) (where \(\theta=\arctan\sqrt{15}\)). The general solution is \[\begin{align*}F(n)&=a2^{n}e^{in\theta}+b2^{n}e^{-in\theta}=\\&=c2^{n}\cos(n\theta)+d2^{n}\sin(n\theta),\end{align*}\] where \[\begin{align*}c&=a+b,\\ d&=i(a-b),\end{align*}\] since \[\begin{align*}\cos x&=\frac{e^{ix}+e^{-ix}}{2},\\ \sin x&=\frac{e^{ix}-e^{-ix}}{2i}.\end{align*}\] Using the initial conditions, we find that \(c=0\) and \(d=2/\sqrt{15}\). The final solution is: \[F(n)=\frac{2}{\sqrt{15}}2^{n}\sin(n\theta).\]
```
from sympy import Function, rsolve
from sympy.abc import n

f = Function('f')
rec = f(n) - f(n - 1) + 4 * f(n - 2)

print(rsolve(rec, f(n)))
print(rsolve(rec, f(n), {f(0): 0, f(1): 1}))
```
```
C0*(1/2 - sqrt(15)*I/2)**n + C1*(1/2 + sqrt(15)*I/2)**n
sqrt(15)*I*(1/2 - sqrt(15)*I/2)**n/15 - sqrt(15)*I*(1/2 + sqrt(15)*I/2)**n/15
```