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?

Solution 1:

$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, .....$

Solution 2:

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$

Solution 3:

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.