2
$\begingroup$

Define the sequence of integers $a_0, a_1, a_2, \cdots$ as follows

$$ a_i = \begin{cases} i+1 & 0 \leq i \leq 2 \\ a_{i-1} + a_{i-2} + 2a_{i-3} & i > 2 \\ \end{cases} $$

Use complete induction to prove that $a_n < 2^n$ for every integer $n \geq 2$

I will prove $a_n < 2^n, \forall n \geq 2$ by using complete induction

Base Case: Three cases $n = 2, 3, 4$

let $n = 2$

$a_{n} = a_{2} = 2 + 1 = 3 < 4 = 2^2 = 2^n$ By definition, and holds

let $n = 3$

$a_{n} = a_{3} = 3 + 2 + 1 = 6 < 8 = 2^3 = 2^n$ By definition, and holds

let $n = 4$

$a_{n} = a_{4} = 4 + 3 + 2 = 9 < 16 = 2^4 = 2^n$ By definition, and holds

Inductive step: let $n > 4$. Suppose $a_j < 2^j$ whenever $2 \leq j < n$. [Inductive hypothesis]

What to prove: $a_n < 2^n$

$a_{n} = a_{i-1} + a_{i-2} + 2a_{i-3}$ [By definition]

$< 2^{n-1} + 2^{n-2} + 2^{n-3+1}$ [By Inductive hypothesis]

$= 2^{n-1} + 2^{n-2} + 2^{n-2}$

$= 2^{n-1} + 2^{n-2 + 1}$

$= 2^{n-1 + 1}$

$= 2^n$

as wanted.

Would this be correct?

$\endgroup$
0
0
$\begingroup$

The second part is fine. But the base case is not just the $n=2$ case. You should have checked it for $n=0$, and $n=1$ too.

$\endgroup$
4
  • $\begingroup$ But it doesn't hold for $n = 0$ or $n = 1$? $\endgroup$
    – Tree Garen
    Dec 1 '18 at 8:01
  • $\begingroup$ You are right. My mistake. But the you should have checked it for $n\in\{2,3,4\}$. Because only then will your inductive proof shows that it works for $n=5$. $\endgroup$ Dec 1 '18 at 8:06
  • $\begingroup$ I'm confused why. Why three numbers? And I thought the base case for recurrence functions was just so we can use "$a_{i-1} + a_{i-2} + 2a_{i-3}$" part but that part holds for all $i > 2$ so wouldn't going all the way to $n = 5$ be redundant? $\endgroup$
    – Tinler
    Dec 1 '18 at 8:14
  • $\begingroup$ Three numbers because each $a_i$ is defined from the three previous terms. So, in order to prove it it holds for $a_5$, you must know that it holds for $a_2$, $a_3$, and $a_4$. $\endgroup$ Dec 1 '18 at 8:26

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.