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?
 A: $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, .....$  
A: For anyone interested in what the definitive Putnam problems/solutions book has to say:

Answer. We have $T_n=n!+2^n$.
Motivation. The hardest part of this problem is guessing the formula. There are not many "well-known sequences" to guess. Observe that the terms are becoming divisible by high powers of $2$ (but not any other prime), and the ratio of the last two terms given is roughly $8$, and the ratio of the previous two is roughly $7$.
Solution. The formula $T_n=n!+2^n$ can be verified by induction. 
Alternatively, set $t_n=n!+2^n$. Clearly $t_0=2=T_0, t_1=3=T_1$ and $t_2=6=T_2$. Also
$$
t_n-nt_{n-1}=2^n-n2^{n-1}.
$$
Now $2^n$ and $n2^{n-1}$ are both solutions of the linear recursion
$$
f_n-4f_{n-1}+4f_{n-2}=0;\tag{1}
$$
this follows from direct substitution. Since $t_n-nt_{n-1}$ is a linear combination of solutions to $(1)$, it must also be a solution. Hence
$$
(t_n-nt_{n-1})-4(t_{n-1}-(n-1)t_{n-2})+4(t_{n-2}-(n-2)t_{n-3})=0,
$$
or equivalently,
$$
t_n = (n+4)t_{n-1}-4nt_{n-2}+(4n-8)t_{n-3}.
$$
Thus $t_n=T_n$, because they are identical for $n=0,1,2$ and satisfy the same third-order recursion $(1)$ for $n\geq 3$. $\blacksquare$
A: 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.
