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!
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.
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.
