Compare inequalities in a proof by induction 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}
$$
 A: 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$.
A: 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$. 
A: 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$.
