Let the sequence Tn be defined by T1 = T2 = T3 = 1 and Tn = Tn-1 + Tn-2 + Tn-3 for n ≥ 4. Use induction to prove that Tn < 2n for n ≥ 4

Let $P(n)$ be the proposition that $T_n<2^n.$

Basis Step

$P(4)$ is true, because $T_4=T_1+T_2+T_3=1+1+1=3<16=2^4.$

Inductive Step

We assume that

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

$T_{k-2}<2^{k-2}$

$T_{k-3}<2^{k-3}$

$T_k=T_{k-1}+T_{k-2}+T_{k-3}<2^k$

Under this assumption

$T_{k+1}=T_{k}+T_{k-1}+T_{k-2}<2^{k}+2^{k-1}+2^{k-2}$

$=2^{k+1}(\dfrac{1}{2}+\dfrac{1}{4}+\dfrac{1}{8})=2^{k+1}(\dfrac{7}{8})<2^{k+1}$

$P(k + 1)$ is true under the assumption that $P(k)$ is true. This completes the inductive step.

We have completed the basis step and the inductive step, so by mathematical induction we

know that $P(n)$ is true for all $n\geq4.$ That is, we have proved that

$T_n=T_{n-1}+T_{n-2}+T_{n-3}<2^n, n\geq 4$