I would appreciate if someone could comment my solution of the task below:
Define the sequence $ \ \ T_1, T_2, T_3,...\ \ $ by $\ \ T_1=T_2=T_3=1 \ \ $ and $ \ \ T_{k+1}= T_{k}+T_{k-1}+T_{k-2}$.
Prove that $\ \ T_{k}≤2^k\ \ $for all $k=1, 2, 3, ...$
The first few numbers are $$LHS =T_1=1≤2^1=2= RHS$$ $$T_2=1≤2^2=4$$ $$T_3=1≤2^3=8$$ $$T_4=3≤2^4=16$$ $$T_5=5≤2^5=32$$
Base case
When $k=1$ we have that $\ \ LHS=T_{1}=1≤2^1=2=RHS\ \ $ the proposition $P(1)$ is true. When $k=2$ we have that $\ \ LHS=T_{2}=1≤2^2=4=RHS\ \ $ the proposition $P(2)$ is true. When $k=3$ we have that $\ \ LHS=T_{3}=1≤2^3=8=RHS\ \ $ the proposition $P(3)$ is true.
Induction step
Let the integer $n≥3$ be given and assume that the propositon $P(k)$ is true for $k=n$ and for $k=n-1$ and for $k=n-2$. Then
$$ T_{n+1}=T_{n}+T_{n-1}+T_{n-2} $$ $$ \ \ \ \ \ ≤2^{n}+2^{n-1}+2^{n-2} $$ $$ \ \ \ \ \ =2^{n-2}(2^{2}+2+1) $$ $$ \ \ \ \ \ <2^{n-2}(2^{2}+2+2) $$ $$=2^{n-2}\cdot 2^{3}$$ $$=2^{n+1}.$$ $$ ∴ T_n≤2^{n}⟹T_{n+1}≤2^{n+1}.$$
Conclusion
By induction principle it follows that $T_n≤2^n$.
Now, to my question. Have I done this induction proof properly? Something missing? Something too much?? Any thing? What??
Here's a more general result.
If $t_{n+1} =\sum_{k=0}^m a_kt_{n-k} $ if, for some $c>0, r > 0$ and some $n_0 > m$, we have $|t_{n_0-k}| \le cr^{n_0-k} $ for $k = 0$ to $m$, and $r^{m+1} \ge \sum_{k=0}^m |a_k|r^{m-k} $
then, for all $n > n_0$, $|t_{n}| \le cr^n $.
Proof.
$\begin{array}\\ |t_{n+1}| &=|\sum_{k=0}^m a_kt_{n-k}|\\ &\le\sum_{k=0}^m |a_kt_{n-k}|\\ &\le\sum_{k=0}^m |a_k|\,|t_{n-k}|\\ &\le\sum_{k=0}^m |a_k|\,cr^{n-k}\\ &= c\sum_{k=0}^m |a_k|r^{n-k}\\ &= cr^{n-m}\sum_{k=0}^m |a_k|r^{m-k}\\ &\le cr^{n-m}r^{m+1}\\ &= cr^{n+1}\\ \end{array} $
In this case, $m=2, a_{0, 1, 2} = 1, 1, 1$ so we want $r^3 \ge r^2+r+1$ and this is true for $r = 2$.
The polynomials $r^m -\sum_{k=0}^m a_kr^{m-k} $ and $r^m -\sum_{k=0}^m |a_k|r^{m-k} $ are known as the characteristic polynomials of the recurrence (usually the form without absolute values is used).
Look it up.