So, here is the question:
For any position 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 \geq 4$.
We have $T(1)=1, T(2)=2, T(3)=3$ $$T(4)=T(3)+T(2)+T(1) = 1+1+1+1 = 3$$ $$T(5) = T(4)+T(3)+T(2) = 3+1+1 = 5$$
Prove that: (Universal n is an element of all positive integers), $T(n)<2^n$
Any suggestions?
Suppose that for all $m\lt n$ we have $T(m)\lt 2^m$. We want to show T(n)\lt 2^n$.
This is certainly true up to $n=3$. Past that, we have $T(n)=T(n-1)+T(n-2)+T(n-3)$. So by the induction assumption we have $$T(n-1)\lt 2^{n-1},\qquad T(n-2)\lt 2^{n-2},\qquad\text{and}\qquad T(n-3)\lt 2^{n-3}.$$
It follows that $$T(n)\lt 2^{n-1}+2^{n-2}+2^{n-3}.$$ We will be finished if we can show that $2^{n-1}+2^{n-2}+2^{n-3}\lt 2^n$. Calculate. We have $2^{n-1}+2^{n-2}+2^{n-3}=\frac{1}{2}\cdot 2^n+\frac{1}{4}\cdot 2^n+\frac{1}{8}\cdot 2^n=\frac{7}{8}\cdot 2^n\lt 2^n$.
