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?

Let's prove it by induction. At first we should establish the base case. $P(n_0) = T_0 = 0! + 2^0 = 1 + 1 = 2$ which is true. One can check the same with $T_1$ and $T_2$.
Now let's establish the strong induction hyphotesis which is as follows. $\forall n \ge 3$ and $ n \in \mathbb{Z} $ we have that $P(n ) = T_k = k! + 2^k $ for $ 1 \ge k \ge n. $
We shall prove that $T_{n+1} = (n+1) + 2^{n+1} $. To do so we're gonna perform the following algebra.
Using our strong hyphotesis and the given formula for $T_n$ set:
\begin{equation}
 T_{n+1} = [(n+1)+4)(n! + 2^n)] -(4(n+1))[(n-1)! + 2^{n-1}] + (4(n-1))[(n-2)! + 2^{n-2}] 
\end{equation}
After being multiplied out, the terms look like:
$$ T_{n+1} = 2^n + (n+1)! + 2^{n+2} + 2^n\cdot n + 4n! -4n! -4(n-1)! -2^{n+1}\cdot n - 2^{n+1} + 4(n-1)! + 2^n\cdot n - 2^n $$
As you can see, many terms will cancel out and in fact all the terms will (check by yourself), except by the following, giving us:
\begin{align*}
 T_{n+1} &= (n+1)! + 2^{n+2} - 2^{n+1} \\ &= (n+1)! + 2^n(2^2 - 2) \\ &= (n+1)! + 2^n(4-2) \\ &= (n+1)! + 2^n(2) \\ &= (n+1)! + 2^{n+1} \blacksquare 
\end{align*}
Quite elegantly done. QED.
