I need help with verifying my solution for the homework question:

For the recurrence $a_{n+3}=a_{n+2}+a_{n+1}+a_n$ where $a_1=a_2=a_3=1$, prove that $a_n\leq 2^{n-2}$, $\forall n>1$

Hint: Use Second principle of induction

First off, I don't even know what is the second principle of induction defined as, so I came up with my own intuitive interpretation of it.

Here goes:

Let $P(k)$ be the statement that $a_n\leq 2^{n-2}$.

Base Case: Let us prove $P(2), P(3)$. $a_2=1\leq 2^{2-2}=1$ and $a_3=1\leq 2^{3-2}=2$.

Inductive Case: Let us prove that $P(k),P(k+1),P(k+2)\implies P(k+3)$. Assume $P(k),P(k+1),P(k+2)$ holds. Now, $a_{k+3}=a_{k+2}+a_{k+1}+a_k\leq 2^{k}+2^{k-1}+2^{k-2}=2^{k-2}(4+2+1)=2^{k-2}(7)\leq 2^{k-2}(8) =2^{k+1}\square$

My confusion comes because the second principle of induction tells us we need to use $P(1),P(2), \dots, P(n)$ to prove $P(n+1)$. However, I only used the previous 3 terms. Is that allowed?

I am also looking for more elegant answers as well! All help will be appreciated. I hope I have done enough research on this question by community standards!

  • 2
    $\begingroup$ Using this principle you have available all the previous values. You use three of the ones you have available. $\endgroup$ – Mark Bennet Aug 8 '15 at 11:28
  • 2
    $\begingroup$ What you are describing as the "second principle of induction" is also called the "strong form" of mathematical induction. Yes, it allowed to call a proof that uses three of the previous values a proof that "uses" this principle (or even if uses only one; the "strong form" includes the "weak form" as a special case). $\endgroup$ – hardmath Aug 8 '15 at 11:34

Yes that is allowed as Mark Bennet says in his comment and your proof is almost correct.

$(1)\quad P(k)$ should be $a_k\le2^{k-2}$ (instead of $n$'s in the superscripts and subscripts) but I'm certain that's a typo.

$(2)\quad $To prove $P(4)$ is true using your inductive argument we need $P(1),P(2),P(3)$ to be true. But $a_1=1>{0.5=2^{1-2}}$. So $P(1)$ is false and you need to manually check that $P(4)$ is indeed true to use induction.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.