Question

Let the sequence T_n be defined by T₁ = T₂ = T₃ = 1 and T_n = T_n-1 + T_n-2 + T_n-3 for n ≥ 4. Use induction to prove that T_n < 2ⁿ for n ≥ 4

Answer 1

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