Find a Formula?

Let us prove by induction that the claim $T_n = n!+2^n$ is true for all $n \ge 0$ .

Proof: For $n=0, 1, 2$ , $T_0 = 0!+2^0 = 2$ , $T_1 = 1!+2^1 = 3$ , $T_2 = 2!+2^2 = 6$ , all as given, hence the claim is true for $n=0, 1, 2$ .

Now, assuming that the claim is true for $n-3$ , $n-2$ and $n-1$ , then:

$\begin{aligned} T_n & = (n+4)T_{n-1}-4nT_{n-2}+(4n-8)T_{n-3} \\ & = (n+4)\left((n-1)!+2^{n-1}\right)-4n\left((n-2)!+2^{n-2}\right)+4(n-2)\left((n-3)!+2^{n-3}\right) \\ & = n! + 4(n-1)! - 4n(n-2)! + 4(n-2)! + (4n+16-8n+4n-8)2^{n-3} \\ & = n! + 2^n \end{aligned}$

Therefore, the claim is also true for $n$ and hence $\boxed{T_n = n!+2^n}$ is true for all $n \ge 0$ .