# Induction Proof: 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}$.

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

• What you've done looks correct. However, I found using the relation symbols of $\lt, \le, =$ at the start & end of each line a bit distracting. Normally, you just use them on the left & don't repeat them on the right of the line above. Also, you state "$T_{n+1}≤2^{n+1}⟺T_n≤2^n$". Technically, you've only shown that using the relation on the right, plus the next $2$ smaller ones, you've shown the relation on the left. I don't think it's needed & personally would not use it. – John Omielan Apr 19 at 20:45
• Also, FYI, you can actually fairly easily determine what $T_n$ is in general. The recurrence relation is an example of Linear Recurrence Relations with Constant Coefficients. You can use a certain technique of a characteristic equation, as described in that link, to directly determine the solution of even considerably more complicated such equations. – John Omielan Apr 19 at 20:46
• Echoing another comment, what you have shown is that $T_n≤2^n.$ implies $T_{n+1}≤2^{n+1}$ and that is all you need for the induction. The implication does not go the other way. – Somos Apr 19 at 22:37
• @John Omielan & Somos: Thanks alot for Your comments and for the link. I've edited my post and I realise the implication. Really helpful. /Pablo – Pablo Apr 19 at 23:38