How to solve $T(n) = 5T(n-1)+6T(n-2)$ iterative solution

Question

$n≥2 , T(0)=1, T(1)=4$

$T(n) = 5T(n-1)+6T(n-2)$

$T(n)$= General rule and $O(n)$ = Big $O$ notation

$T(n)=?$

$O(n)=?$

I tried to use the information provided.

$T(2) = 5.4 + 6.1=26$

$T(3) = 5.26 + 6.4 = 154$

$T(4) = 5.154 + 6.26 = 926$

$T(n) = ...............?$

How do I create the pattern?(Please don't tell me to study this again. I tried and failed.)

Answer 1

I will give you an specific method to solve this. If you want more information about this topic this equation is called a linear recurence equation (they can be solved in many different methods, and I think it is a nice subject to study). Since $T(n) = 5T(n-1)+6T(n-2)$ we can find the characteristic polynomial of the recurence which is $x^2-5x-6$. This polynomial has roots $x=-1,6$, so the general term is: $$T(n)=a(-1)^n+b6^n$$ With the initial conditions T(0)=1, T(1)=4 we can find the values of $a$ and $b$: $$a+b=1$$ $$-a+6b=4$$ This gives us $a=\frac{2}{7}$ and $b=\frac{5}{7}$ and hence: $$T(n)=\frac{2}{7}(-1)^n+\frac{5}{7}6^n$$

From this, one gets that: $$O(n)=\frac{5}{7}6^n$$ (I am not sure if this is what you want as $O(n)$)

Answer 2

The general method to solve this kind of recurrence is to replace $T_n=r^n$:

$$r^n-5r^{n-1}-6r^{n-2}=0\rightarrow r^2-5r-6=0$$

with the roots $$r_1=6, r_2=-1,$$ and the general term is:

$T_n=A6^n+B(-1)^n$, with $T_0=1, T_1=4$.

So we have to solve the system:

$A+B=1$

$6A-B=4\rightarrow A=\frac{5}{7}, B=\frac{2}{7}\rightarrow$

$T_n=\frac{5\cdot6^n+2(-1)^n}{7}$