Compare inequalities in a proof by induction

Question

I am solving a proof by induction example. But I ended up with my hypothesis

$$ a_{n-1} \geq \frac{2^n}{2}+n^2-2n+1 $$

and my inductive step

$$ a_{n-1} \geq \frac{2^n}{2}+\frac{n^2}{2}-\frac{n}{2}. $$

How can I show that if I am assuming that my hypothesis is true then my inductive step is also true?

It seems to me that I can compare both equation's right hand sides as

$$ \frac{2^n}{2}+n^2-2n+1 \geq \frac{2^n}{2}+\frac{n^2}{2}-\frac{n}{2} \Leftrightarrow -\frac{n^2}{2}-\frac{3}{2} n \geq -1 \Leftrightarrow -n^2-3n \geq -2. $$

But now I just ended up with a neq inequality that I have to proof?

Edit

I am proving that $a_n \geq 2^n + n^2$ for all natural numbers. $a_n$ is defined by the recursive definition $$ a_n = \begin{cases} 1 & n=0 \\ n+2 a_{n-1} & n \geq 1 \end{cases} $$

Answer 1

First of all to prove the induction step from your hypothesis note that $2(n-1)^2\geq n(n-1)$ for all $n\geq 2$

To prove the problem, note that

$\begin{align}a_{n+1}-2^{n+1}-(n+1)^2-a_n+2^n+n^2 & =\left(a_{n+1}-a_n\right)-2^n-2n-1\\&=a_n+(n+1)-2^n-2n-1\\&=a_n-2^n-n>0\end{align}$

Which is true if you assume that $a_n>2^n+n^2$.

Answer 2

Our induction hypothesis is that the inequality holds at $n=k$. We want to ahow that the inequality holds at $k+1$.

So we know that $a_k\ge 2^k+k^2$. We want to show that $a_{k+1}\ge 2^{k+1}+(k+1)^2$. Note that $$a_{k+1}=k+1+2a_k\ge 2(2^k+k^2)+(k+1)=2^{k+1} +2k^2+k+1.$$ We will be finished if we can prove that $2k^2+k+1\ge (k+1)^2$, or equivalently that $k(k-1)\ge 0$. This is clear, since we have equality at $k=0$ and $k=1$, while $k^2-k\gt0$ if $k\gt 1$.

Answer 3

Alternatively, if you prefer a more direct approach, the finite difference method is really useful.

We have $$ \begin{array}{c|l|c|r} n & a_n & b_n=a_{n+1}-a_{n} & c_n=(a_{n+2}-a_{n+1})-(a_{n+1}-a_{n}) \\ \hline 0 & 1 & 2 & 3\ \\ 1 & 3 & 5 & 6\ \\ 2 & 8 & 11& 12\ \\ 3 & 19 & 23 & 24\ \\ 4 & 42 & 47 & \vdots \\ 5 & 89 & \vdots & \vdots \\ \vdots&\vdots&\vdots&\vdots \end{array} $$ Clearly, $$c_n=3\cdot2^n,$$ whence $$b_n=2+3\sum_{i=0}^{n-1}2^i=2+3(2^n-1)=3\cdot2^n-1.$$ Thus, the general formula for $a_n$ is $$a_n=1+\sum_{i=0}^{n-1}\left(3\cdot 2^i-1\right)=1+3\sum_{i=0}^{n-1}2^i-n=3\cdot2^n-n-2.$$ So we prove by induction $$a_n\ge 2^n+n^2$$$$3\cdot2^n-n-2\ge2^n+n^2$$$$2^{n+1}\ge n^2+n+2.\tag{P(n)} $$ Basis: P($0$): $2\ge2$ is true.

Inductive step: Assume P$(k)$ holds. P$(k+1)$ is equivalent to$$2^{k+2}\ge(k+1)^2+(k+1)+2$$ $$ 2\cdot2^{k+1}\ge k^2+2k+1+k+3$$$$2^{k+1}\ge \frac{k^2+3k+4}{2}.\tag{1}$$ Since $$2^{k+1}\ge k^2+k+2$$ by hypothesis, and $$k^2+k+2\ge \frac{k^2+3k+4}{2}\\ 2k^2+2k+4\ge k^2+3k+4 \\ k^2\ge k,$$ $(1)$ holds, and thus P$(n)$ is true for all $n$.