Proofs by strong induction

Question

I am trying to solve the following problem using strong induction, the problem is the following:

For any positive integer $n$, let $T_n$ be the number $1$ if $n<4$ and the number $T_{n − 1} +T_{n − 2} +T_{n − 3}$ if $n\ge 4$.

We have $T_1 =1, T_2 =1, T_3 =1, T_4 =T_3 +T_2+T_1=1+1+1=3$, $T_5 =T_4 +T_3 +T_2 =3+1+1=5$, etc.

Prove that: $\forall n \in \Bbb{Z}^+$, $T_n <2^n$ $\;$

Sadly, I don't even know where to start this question!

Answer 1

You don't have to use strong induction.

For $n=4$, the proposition is true. Let's suppose it's true for $n-1$, let's see this implies that it's also true for $n$.

We know that:

$$T_{n-1} < 2^{n-1}$$

On the other hand:

$$T_n < 2^n \Leftrightarrow T_n < 2^{n-1} \cdot 2$$

So if we see that $\frac{T_n}{2} < T_{n-1}$, we are done, because $T_{n-1} < 2^{n-1}$.

$$\frac{T_n}{2}< T_{n-1}$$

$$T_{n-1}+T_{n-2} + T_{n-3} < 2 T_{n-2} + 2T_{n-3} + 2T_{n-4}$$

$$0 < T_{n-2}+ T_{n-3} + 2 T_{n-4}$$

Which is true.

Answer 2

Strong induction says that if you can show that a proposition which is true for all m < n is also true for n then it is true for all n.

In this case, for n >= 4 you can show that this is true by showing that Tn < $(7/8) 2^n $ by adding up $2^{n-1} + 2^{n-2} + 2^{n-3}$

For n = 1, 2, 3 you have already shown it.