Putnam 1990 A1 Induction Help 
A1. $(150,9,1,0,0,0,0,0,1,1,6,33)$
Let $$T_0=2,\quad T_1=3,\quad T_2=6,$$ and for $n\ge3$, $$T_n=(n+4)T_{n-1}-4nT_{n-2}+(4n-8)T_{n-3}.$$
The first few terms are $$2,3,6,14,40,152,784,5168,40576,363392.$$
Find, with proof, a formula for $T_n$ of the form $T_n=A_n+B_n$, where $(A_n)$ and $(B_n)$ are well-known sequences.

I found that:
$$T_n - n! = 2^n$$ and verified that $T_0 = 2^0 + 1 = 2$
Hence,
$$T_n = 2^n + n!$$
I need to prove that:
$$T_{n+1} = 2^{n+1} + (n+1)!$$
Which I can't do.
I went back and stated:
$$T_{n+1} = nT_{n} + T_n + 4T_n - 4nT_{n-1} - 4T_{n-1} + 4T_{n-2} + T_{n-2} - 8T_{n-2}$$
What to do next?

$T_n = 2^n + n!$ is true for $n=0,1,2$.  Let's assume it is also true for $n=k,k+1,k+2$ where,


*

*$T_{k} = 2^{k} + (k)!$  

*$T_{k+1} = 2^{k+1} + (k+1)!$  

*$T_{k+2} = 2^{k+2} + (k+2)!$.  


Then, let's prove it for n=k+3.
Using  $ \; T_n = (n+4) T_{n-1} -4n T_{n-2} + (4n-8)T_{n-3}$, we get  
$T_{k+3} = (k+7) \cdot 2^{k+2} + (k+7)(k+2)! - (k+3) \cdot 2^{k+3} - 4(k+3)(k+1)! + (k+1) \cdot 2^{k+2} + 4(k+1)! = \\ = 2^{k+2} (k+7 - 2k - 6 + k + 1) + (k^2 +9k+14 -4k -12 + 4) (k+1)! = \\ = 2^{k+2} \cdot 2 + (k^2 +5k+6)(k+1)! = 2^{k+3} + (k+3)!$
Case closed....

Irrelevant PS.
$T_{k+1} - T_k = 2^k + k \cdot k! = T_k + (k-1)k! \; \Rightarrow T_{k+1} = 2T_k + (k-1)k!$

Just came to mind:
Using $ \; T_n = (n+4) T_{n-1} -4n T_{n-2} + (4n-8)T_{n-3}$ we get
$$T_n - 2T_{n-1} = (n+2)(T_{n-1} - 2T_{n-2}) - (2n-4)(T_{n-2} - 2T_{n-3})$$
Let's assume $A_n = T_n - 2T_{n-1}$, we get
$$A_n = (n+2)A_{n-1} - (2n-4)A_{n-2} \; \; \; \; for \; \; n \ge 3.$$
$A_n = -1, 0, 2, 12, .....$  
