3
$\begingroup$

The sequence $a_n, n \in \mathbb{N}, n \geq 1$ is defined recursively as follows: $a_1 = a_2 = a_3 = 1, a_n = a_{n-1} + a_{n-2} + a_{n-3}, n \geq 4$. Prove by induction that $a_n < 2^n$.

My proof:

First step: For $n=4$, we have $a_4 = 1+1+1 < 2^4$, so it's correct for $n=4$.

Induction hypothesis: $a_m = a_{m-1} + a_{m-2} + a_{m-3}, \forall m \in \mathbb{N}$ such that $4 \leq m \leq k$.

Proof: $a_{k+1} = a_k + a_{k-1} + a_{k-2} < 2^{k+1}?$

$$a_{k+1} = a_k + a_{k-1} + a_{k-2} \stackrel{def. seq.}{=} (a_{k-1} + a_{k-2} + a_{k-3}) + a_{k-1} + a_{k-2} $$ $$ a_{k+1}= 2a_{k-1} + 2a_{k-2} + a_{k-3} < 2( a_{k-1} + a_{k-2} + a_{k-3}) $$ $$2( a_{k-1} + a_{k-2} + a_{k-3}) \stackrel{def. seq}{=} 2a_k \stackrel{ind. hyp.}{<}2 \cdot2^k = 2^{k+1}$$

So we conclude that $a_{k+1} < 2^{k+1}$. We also conclude that we didn't need to use strong induction because mathematical induction sufficed as we only used the induction hypothesis for $m=k$.

I have two questions:

  1. Is my proof correct, with regards to notation and such? I'm especially worried about my induction hypothesis, our teacher didn't explain strong induction well so I want to know if my induction hypothesis uses strong induction correctly (even though we didn't need it in this particular case, I reckon)
  2. Is it correct that we didn't need to use strong induction for this proof? This question is kind of a subset of question 1.
$\endgroup$
2
  • 1
    $\begingroup$ See also this question concerning the question of using strong induction. It is equivalent to weak induction, so it does not matter. $\endgroup$ Commented Sep 15, 2016 at 19:22
  • $\begingroup$ @DietrichBurde My professor doesn't want us to use strong induction when mathematical induction suffices. If we do, he wants us to point out we didn't have to. I don't know why, but that's why I find it important. $\endgroup$ Commented Sep 15, 2016 at 20:31

2 Answers 2

1
$\begingroup$

This should be a comment, but is too long to fit in the given space. Actually, you don't even need induction. The characteristic polynomial associated with the given sequence is $$ p(t)=t^3-t^2-t-1 $$ that has three distinct roots $\alpha,\beta,\gamma$, with one of them being real, say $\alpha$ (so $\beta$ and $\gamma$ are conjugates). By the theory of linear recurrence relations, $a_n$ has the explicit form $$ a_n = A\alpha^n+B\beta^n+C\gamma^n $$ where the absolute constants $A,B,C$ depend on the initial conditions $a_1=a_2=a_3=1$.
We have $p(t)(t-1)=t^4-2t^3+1$, hence $p\left(2-\frac{1}{8}\right)>0$ and $p\left(2-\frac{1}{4}\right)<0$, so $\alpha$ belongs to the interval $\left(2-\frac{1}{4},2-\frac{1}{8}\right)$. By Vieta's formulas, $\alpha\beta\gamma=1$, hence $$ \|\beta\|=\|\gamma\| \leq \frac{1}{\sqrt{2-\frac{1}{4}}}\leq 1 \leq \|\alpha\|$$ and $$ a_n \leq |A|\cdot\left(2-\frac{1}{8}\right)^n+2|\text{Re}\, B|. $$ You may now use the initial conditions to prove $|A|\leq\frac{1}{4}$ and $2|\text{Re}\,B|\leq\frac{4}{3}$. It follows that $$ a_n \leq \frac{1}{4}\left(2-\frac{1}{8}\right)^n+\frac{4}{3}.$$

$\endgroup$
1
$\begingroup$

Yes, your proof is correct. You have avoided using of strong induction by digging deeply into the recursion.

Some strong induction proofs require the induction hypothesis be right for any integer between the basis and $n$, but for this problem, if you use strong induction, you only need the induction hypothesis holds for three numbers $n-2$, $n-1$, and $n$. In my opinion, this is similar to what you have done, that is, using the recursion twice.

$\endgroup$
4
  • 1
    $\begingroup$ @Leucippus The author was asking whether he is right that he has not used strong induction, and I confirmed that. I think this is an answer. Yes, it is true that I did not provide a solution, or a proof. I don't intend to argue, but we are talking about math and everything needs to be precise. $\endgroup$
    – S. Y
    Commented Sep 16, 2016 at 0:14
  • $\begingroup$ The second part of the Question is about using strong induction, but the first part asks for checking if the proof offered is correct. At a minimum you should weigh in on that, as perhaps you intend us to accept implicitly. But one liners are rarely good Answers, and you can no doubt provide more to benefit future Readers on this topic, e.g. how was the recursion set up to avoid strong induction? $\endgroup$
    – hardmath
    Commented Sep 16, 2016 at 0:31
  • $\begingroup$ @hardmath Yes you are right that I did not say it out that the proof $\endgroup$
    – S. Y
    Commented Sep 16, 2016 at 0:33
  • $\begingroup$ @hardmath You are right that I should have said clearly his proof is right. $\endgroup$
    – S. Y
    Commented Sep 16, 2016 at 0:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .