How to solve $T(n) = 5T(n-1)+6T(n-2)$ iterative solution $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.)
 A: 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)$)
A: 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}$
