I would like to see if this is a correct induction proof and whether or not this is a good setting out of it
A sequence is defined by $$a_n = a_{n-1} + a_{n-2} + a_{n-3}$$ for $n\geq 3, a_0 = 1, a_1 = 2, a_2 = 4$.
Prove that $a_n \leq 4^n$ for all $n\in\mathbb{N}$.

Let $P(n)$ be the proposition that $$''a_n\leq 4^n{''}.$$

Now since we have $a_0 = 1 = 4^0 \leq 4^0$ then $a_0 \leq 4^0$.
Also, $a_1 = 2 < 4 \leq 4 = 4^1$ then $a_1 \leq 4^1$.
Also, $a_2 = 4<16 = 4^2 \leq 4^2$ so $a_2 \leq 4^2$.

Hence, $P(0),P(1),P(2)$ are true.

Now, let $k-3\in\mathbb{N}$ and suppose $P(k-3),P(k-2),P(k-1)$ is true.
We must show that $P(k)$ is true.

Now by definition $$\begin{align}a_n &= a_{n-1} + a_{n-2} + a_{n-3} \\ &\leq 4^{n-1} + 4^{n-2} + 4^{n-3} \qquad \text{by the inductive hypothesis}\\ &= 21\times 4^{k-3} \\ &\leq 64\times 4^{k-3} \\ &= 4^{k}.\end{align}$$

Hence, $P(k)$ is true if $P(k-3),P(k-2),P(k-1)$ is true for $k\geq 3$.
So by induction, $P(n)$ is true for all $n\in\mathbb{N}$.

Would appreciate any advice.

  • 2
    $\begingroup$ Looks good to me. $\endgroup$ – learning Nov 10 '17 at 8:02

Suppose that $P(n)$ is true and prove it for $P(n+1)$

$ a_n = a_{n-1} + a_{n-2} + a_{n-3}\quad $ by the inductive hypothesis

if we suppose that $P(k)$ is true for any $1\leq k\leq n$ we are using strong induction

We must prove that

$a_{n+1}\leq 4^{n+1}$

$a_{n+1}=a_n + a_{n-1} + a_{n-2} \leq 4^n+4^{n-1}+4^{n-2}=4^{n-2}\left(4^2+4+1\right)=21\cdot 4^{n-2}\leq 64\cdot 4^{n-2}=4^{n+1}$


Hope this helps

| cite | improve this answer | |
  • $\begingroup$ Is my assumption sentence incorrect then? $\endgroup$ – OneGapLater Nov 10 '17 at 9:13
  • $\begingroup$ Induction works in this way: P(1) is true, if $P(n)$ is true then $P(n+1)$ is true. End. You assumed $P(n-2),P(n-1),P(n)$ true and proved $P(n+1)$ then formally you used strong induction, which is explained in my answer. The core of your proof is correct. My answer is just to adjust some formal detail. $\endgroup$ – Raffaele Nov 10 '17 at 11:08
  • $\begingroup$ I see, so formal strong induction is assuming (in my case) for all $3\leq i \leq k$ and $k\geq 3$ is true. (but really, I only need to use the values $i=k-3,k-2,k-1$ in my proof?) $\endgroup$ – OneGapLater Nov 11 '17 at 4:15
  • $\begingroup$ @ActuarialStudent101 Formally you did not use strong induction because your hypothese was not the statement "$P(i)$ is true for all $i<k$". With normal induction ("$P(n)$ true implies $P(n+1)$ true") you cannot reach your goal. Nevertheless you did reach your goal with normal induction. This because you focused not on $P(n)$ but on the $Q(n)$ in my answer. Beautiful about induction is that sometimes you can make things easyer by enforcing the hypothese. A possible bonus is then that you also prove more. $\endgroup$ – drhab Nov 11 '17 at 9:00

Your proof is okay.

Actually you proved that $\forall n\in\mathbb N\, [Q(n)]$ where $Q(n)$ is stated by:$$\forall n\in\mathbb N [P(n)\wedge P(n+1)\wedge P(n+2)]$$

Of course $\forall n\in\mathbb N\, [P(n)]$ is a direct consequence of $\forall n\in\mathbb N\, [Q(n)]$

| cite | improve this answer | |

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