Proving a sequence formula using induction Suppose for $T_n$:
$$T_n=(n+4)T_{n-1}-4nT_{n-2}+(4n-8)T_{n-3}$$
$$T_0=2,\quad T_1=3,\quad T_2=6$$
For integer, $n \ge 3$
I conjectured that:
$$T_n = 2^n + n!$$
The above is actually TRUE.
Using induction I have to prove that. 
How do I go about proving:
$$T_{n+1} = 2^{n+1} + (n+1)!$$
Of course I will use:
$$T_n=(n+4)T_{n-1}-4nT_{n-2}+(4n-8)T_{n-3}$$
But can I for example change:
$$T_{n} = 2^{n} + n!$$
And let $n \to n-1$ to get:
$$T_{n-1} = 2^{n-1} + (n-1)!$$
I would say no? Because I havent yet proved $T_n$, so how can I change $n \to n-1$?
Thanks!
 A: We're going to use a form of induction known as strong induction (at least in my graph theory class it is known as this).  Instead of only assuming the term (n-1) holds true, we will assume that all cases are valid for integers less than n.  However, we still need a base case which was missing from your attempt.  $T_3 = (3+4)*6 -4*3*3 +4*2 = 14 = 2^3 +3!$, thus we can proceed with our induction.  To make things absolutely clear, we are going to assume that your formula $T_n = 2^n +n!$ holds true for all integers less than n.  Thus, by our induction hypothesis.  $$T_{n-1} =2^{n-1} + (n-1)! $$$$T_{n-2} =2^{n-2} + (n-2)! $$ $$T_{n-3} = 2^{n-3} + (n-3)!$$
Okay, now we're all set up.  We know that $T_n =(n+4)T_{n-1}-4nT_{n-2}+(4n-8)T_{n-3}$.  Substituting the equations we got from our induction hypothesis yields:  $$T_n=(n+4)(2^{n-1}+(n-1)!) -4n(2^{n-2}+(n-2)!)+(4n-8)(2^{n-3}+(n-3)!)$$ $$ = n! +n2^{n-1} + n^{n+1} + 4(n-1)!-n2^n-4n(n-2)! +n2^{n-1}+4n(n-3)!-2^n-8(n-3)!$$Yes, this is getting quite messy, but notice that we have a $2^{n+1}-2^n = 2^n$.  Substituting this, we arrive at: $$T_n= n! +2^n+n2^{n-1} +  4(n-1)!-n2^n-4n(n-2)! +n2^{n-1}+4n(n-3)!-8(n-3)!$$After some algebra, you will see that all the terms of the equation except the first 2 actually combine to zero, which gives us the correct equation for $T_n$.  If you really want to see it, leave me a comment and i'll supply you with the steps I took, but it is so much more satisfying to get it by yourself.  Good luck!
