0
$\begingroup$

Let $a_1,a_2,a_3,\cdots$ be the sequence of integers defined by $a_1=1$, $a_2=3$, $a_3=7$ and$$a_i=a_{i−1}+a_{i−2}+a_{i−3}$$ for each integer $i≥4$. Prove by strong induction that $a_n<2^n$ for all integers $n≥1$.

To be honest, I don't really understand the concept of strong induction like what is the difference between strong and normal induction. Based on the question above I have already done a base case:

  • When $n = 1$, $a_i = 1$ and $1<2^1$ therefore true for $n = 1$.
  • When $n = 2$, $a_i = 3$ and $3<2^2$ therefore true for $n = 2$.
  • When $n = 3$, $a_i = 7$ and $7<2^3$ therefore true for $n = 3$.

However, I am not too sure about the induction step. I am a bit confused on how to implement this statement ($a_i = a_{i−1} + a_{i−2} + a_{i−3}$ for each integer $i ≥ 4$) into the induction. What approach should I take to prove the statement is true?

$\endgroup$
1
$\begingroup$

The difference between regular induction and strong induction is that in regular induction you assume some predicate $P$ is true of $k$, then show from this that $P$ is true of $k+1$. Along with a base case this proves the predicate is true for all naturals. In strong induction you assume $P$ is true for all naturals less than or equal to $k$ and prove it for $k+1$.

In this problem your equation involves $a_{n-1}, a_{n-2},$ and $a_{n-3}$. You want to use the fact that $a_k \lt 2^k$ for each of them. This is what makes it strong induction as you use three instances of the induction hypothesis. So assume $a_k \lt 2^k$ for all $k \lt n$ and say $$a_n=a_{n-1}+a_{n-2}+a_{n-3}\\ \lt 2^{n-1}+2^{n-2}+2^{n-3}\\ =7\cdot 2^{n-3} \\\lt 8 \cdot 2^{n-3}\\=2^n$$ where we used the three instances going from the first line to the second.

$\endgroup$
0
$\begingroup$

Assume that $a_k<2^k$ for all $k<i$

$a_i=a_{i-1}+a_{i-2}+a_{i-3}\quad$ < $\quad2^{i-1}+2^{i-2}+2^{i-3}$

$RHS = 7*2^{i-3}$ < $8*2^{i-3}$ = $2^i$

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