Question

Solve the following recurrence relations
i) Fn= Fn-1 +Fn-2 where a1=a2=1
ii) an=2an-1 - an-2 +2 where a1 = 1 and a2 = 5

Answer 1

i) Write down the characteristic equation:

$x^2 = x + 1$

$x^2 -x -1 =0$

$x_1 =\frac{1 + \sqrt5}2 = \phi ; \ x_2 = \frac {1 -\sqrt 5}2 =\psi$

$F_n = ax_1^n +bx_2^n$

$a*\phi +b*\psi = 1\ and\ \ a*\phi^2 +b*\psi^2 = 1$

$a*\phi = 1 - b*\psi;$

$(1-b*\psi)*\phi +b*\psi^2 = 1$

$\phi*\psi = \frac{1- 5}4 = -1;$

$\phi +b + b*\psi^2 = 1$

$b*(1+\psi^2) = 1 -\phi$

$\psi^2 > 0;\ \ 1+ \psi^2 >0$

$b = \frac {1-\phi}{1+\psi^2} = \frac {1- \frac{1+\sqrt 5}2}{1+ (\frac{1-\sqrt5}2)^2} =$

$= \frac{\frac{1-\sqrt5}{2}}{\frac{2*5 -2*\sqrt5}4} = \frac{\frac{1-\sqrt5}{2}}{-\sqrt5*\frac{(1 - \sqrt5)}2}=-\frac {1}{\sqrt5}$

$\phi > 0;\ \ a = \frac{1 + \frac{\psi}{\sqrt5}}{\phi} =\frac{1+\frac{\frac{1-\sqrt5}{2}}{\sqrt5}}{\frac{1+\sqrt5}{2}}=$

$=\frac{\frac{2*\sqrt5+1-\sqrt5}{2\sqrt5}}{\frac{1+\sqrt5}{2}} =\frac{\frac{1+\sqrt5}{2\sqrt5}}{\frac{1+\sqrt5}{2}}=$

$=\frac{1}{\sqrt5}*\frac{\frac{1+\sqrt5}{2}}{\frac{1+\sqrt5}{2}} = \frac{1}{\sqrt5}$

$F_n = \frac{\phi^n}{\sqrt5} - \frac{\psi^n}{\sqrt5}= \frac{\phi^n - \psi^n}{\sqrt5};$

ii) $a_3 = 2*5 -1 + 2 = 10 + 1 = 11$

$a_{n+1} = 2a_{n} - a_{n-1} + 2;$

$a_n = 2a_{n-1} - a_{n-2} + 2;$

From the first equation subtract the second:

$a_{n+1} - a_n = 2a_n - a_{n-1} + 2 - 2a_{n-1} + a_{n-2} - 2$

$a_{n+1} = 3a_n - 3a_{n-1} + a_{n-2} \ for \ n \ge 3$

Therefore, for $n \ge 4: a_n = 3a_{n-1} - 3a_{n-2} + a_{n-3};$

Write down the characteristic equation:

$x^3 - 3x^2 +3x -1 = 0$

$(x-1)^3= 0$

$x_{1,2,3}= 1;$

$a_n = k_1*1^n + k_2*n*1^n + k_3*n^2*1^n =$

$=k_1+ k_2*n + k_3*n^2;$

The system of three equations:

$k_1+ k_2 + k_3= a_1 = 1$

$k_1+ k_2*2 + k_3*4= a_2 = 5$

$k_1+ k_2*3 + k_3*9= a_3 = 11$

Subtract the first from the second:

$k_2 + k_3*3= 4$ (iv)

Subtract the second from the third:

$k_2 + k_3*5= 6$ (v)

Subtract (iv) from (v):

$k_3*2 = 2$

$k_3 = 1$

From this and (iv):

$k_2 +3 = 4$

$k_2 = 1$

From these and the first:

$k_1 + 1 +1 = 1$

$k_1=-1$

$a_n = -1 + n + n^2 = n^2 +n -1.$

Answer: i) $F_n = \frac{\phi^n - \psi^n}{\sqrt5}$

ii) $a_n = n^2 +n -1$