0
$\begingroup$

Suppose that the numbers $a_n$ are defined inductively by $a_1 = 1, a_2 = 2, a_3 = 3$, and $a_n = a_{n−1} + a_{n−2} + a_{n−3}$ for all $n \geq 4$. Use the Second Principle of Finite Induction to show that $a_n < 2^n$ for every positive integer $n$.

Source: David Burton's Elementary Number Theory, p. 8, question 13 of "Problems 1.1".

$\endgroup$
  • 2
    $\begingroup$ Can you show your attempt? $\endgroup$ – wythagoras May 3 '15 at 15:46
  • $\begingroup$ Hint: Try the Second Principle of Finite Induction.... $\endgroup$ – N. S. May 3 '15 at 15:50
  • $\begingroup$ That is given in the problem statement. $\endgroup$ – wythagoras May 3 '15 at 15:50
  • 1
    $\begingroup$ ${111}_2 < {1000}_2$. $\endgroup$ – user21467 May 3 '15 at 15:54
0
$\begingroup$

For $a_1, a_2, a_3$ it is trivial.

Now assume that $a_{k} < 2^k$, $a_{k+1} < 2^{k+1}$, $a_{k+2} < 2^{k+2}$.

Therefore $$a_{k+3} = a_k+a_{k+1}+a_{k+2} < 2^k + 2^{k+1} + 2^{k+2} = 7\cdot2^k < 2^{k+3}$$

That completes the induction and thereby the proof, QED.


You don't seem to get the idea of induction. The normal induction is:

  • Show that it holds for $n=1$
  • Show that it if it holds for $n=k$ (called the induction hypothesis), then it holds for $n=k+1$.

In this case we use induction with three hypotheses:

  • Show that it holds for $n=1$, $n=2$ and $n=3$.
  • Show that it if it holds for $n=k$, $n=k+1$ and $n=k+2$ (called the induction hypothesis), then it holds for $n=k+3$.
$\endgroup$
0
$\begingroup$

Hint: Consider instead the sequence defined by the same initial values and $\displaystyle a_n = \sum_{k=0}^{n-1} a_k$ for $n \geq 4$.

$\endgroup$

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.