1

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.

OneGapLater
  • 820
  • 1
  • 9
  • 22

2 Answers2

1

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}$

proved

Hope this helps

Raffaele
  • 26,371
  • Is my assumption sentence incorrect then? – OneGapLater Nov 10 '17 at 09:13
  • 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. – Raffaele Nov 10 '17 at 11:08
  • 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?)     – OneGapLater Nov 11 '17 at 04:15
  • @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. – drhab Nov 11 '17 at 09:00
1

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)]$

drhab
  • 151,093