Induction proof to prove inequality? I'm quite comfortable proving by induction, but I've stumbled upon an exercise where you need to prove a inequality using induction, something I have never done before, and where I'm absolutely clueless how to start. It goes as follows:
The numbers $a_k$ with $k\in \mathbb{N}$ is given by $a_0=1, a_1=2$ and $$a_k=5a_{k-1}-4a_{k-2}$$ for $$k\leqq2$$
Use proof by induction to prove $$a_{k-1}\leqq a_{k} \leqq 4a_{k-1}$$
If someone knows the answer it would be very much appreciated if you would share your wisdom :)
Thanks in advance
 A: At least in most elementary cases, induction is always : base case, induction case. What are we trying to prove? That $a_{n} \leq a_{n+1} \leq 4a_n$ for all $n \geq 0$.
Base Case
The base case is to check that this is true for $n=0$. This gives $a_0 \leq a_1 \leq 4a_0$. This is true, since the inequality becomes $1 \leq 2 \leq 4$.
The base case is clear by checking that $1<2<4$.
Induction Case
For the induction case, we'll assume that $a_{k-1} \leq a_k \leq 4a_{k-1}$ holds true up till index $n$, and prove it for $n+1$. In fact, we only need to assume that $4a_{n-1} \leq a_n \leq 4a_{n-1}$.
Now, remember these simple facts, which we will be using (all variables below take values in the real numbers) :

*

*If $y\geq z$ then for any $x$ we have $x+y > x+z$. (Hate $2$, so I'll skip it)


*If $y \geq z$ and $x<0$ then $xy \leq xz$ (note the sign reverses)
That's what we need, these two facts.

We want to prove $a_{n+1} \geq a_{n}$ first. Remember that $a_{n+1} = 5a_{n} - 4a_{n-1}$. Now, from our induction hypothesis, we know that $a_n \geq a_{n-1}$. Multiply by $-4>0$ and use point $3$ to get $-4 a_n \leq -4a_{n-1}$. Now, add $5a_n$ to both sides, then use point $1$ to get $5a_n - 4a_n \leq 5_n - 4a_{n-1}$. The left hand side is $a_n$, the right hand side is $a_{n+1}$ so $a_n \leq a_{n+1}$.

Now let's prove that $a_{n+1} \leq 4a_n$. Once again, $a_{n+1} = 5a_{n} - 4a_{n-1}$. We know that $a_n \leq 4a_{n-1}$. Again, multiply by $-1$ and use point $3$ to get $-a_n \geq -4a_{n-1}$. Now, add $5a_{n}$ to both sides and use point $1$ to get $5a_n - a_n \geq 5a_n - 4a_{n-1}$. The left side is $4a_n$ , the right side is $a_{n+1}$ so $4a_n \geq a_{n+1}$.

Thus $a_n \leq a_{n+1} \leq 4a_n$ and the induction is complete!
