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


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

  • $\begingroup$ 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. $\endgroup$ – John Omielan Apr 19 at 20:45
  • $\begingroup$ 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. $\endgroup$ – John Omielan Apr 19 at 20:46
  • $\begingroup$ 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. $\endgroup$ – Somos Apr 19 at 22:37
  • $\begingroup$ @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 $\endgroup$ – Pablo Apr 19 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.