100-level discrete maths, induction problem, prove $n^2 \ge 2n + 1$ I've just run into this problem, and was able to go as far, and understand the induction step up to the bolded section. The last part I found in the back of my book, italicized, I can't understand.
Use induction to prove: $n^2\geq 2n + 1$ for all $n\in \mathbb{N}$ and $n\geq 3$.
Base: $3^2\geq 6+1$.
Induction Hypothesis: Assume that $k^2\geq 2k+1$ for $k\geq 3$.
Induction Step: $(k + 1)^2=k^2+2k+1\geq 2k+1 + 2k + 1 = 2(k + 1) + 2k \geq 2(k + 1) + 1$
I went as far as $(k + 1)^2 \geq 2(k+1) + 1$?
Any help, much appreciated
 A: You have assumed that $\color{blue}{k^2}\geq\color{#af5500}{2k+1}$ for some specific $k$. So $$\begin{align}(k+1)^2&=\color{blue}{k^2}+2k+1\\
&\geq\color{#af5500}{2k+1}+2k+1\\&=2(k+1)+2k\\&\geq2(k+1)+1\end{align}$$ where the last inequality is because $2k>1$.
A: By your expansion, 
$$\left(k^2\geq 2\,k+1\right)\;\Rightarrow\; \left((k+1)^2 \geq 4\,k+2\right)\tag{1}$$
since, as you have found, $(k+1)^2 = k^2 + 2\,k+1 \geq 2\,(2\,k+1)$ by the predicate on the LHS of the $\Rightarrow$ in (1).
But, for $k\geq 1$, we also have $4\,k+2 > 2\, k+3 = 2(k+1)+1$, hence your induction step follows from (1) together with $4\,k+2 > 2 k+3$.
You've clearly got the right idea: you simply seem to be confusing yourself with symbols: this happens to most humans often so (as I have needed to do many times), if this happens to you, I susgest you write the above out in terms of a predicate with a formal definition $P:\mathbb{N}\to\{\text{true},\,\text{false}\}$ (in this case $P(n) = (k^2\geq 2\,k+1)$) and manipulate, with standard first order rules of inference, the truth functions beginning from $P(n_0)=\text{true}$ for the induction basis and $P(n)\Rightarrow P(n+1)$ for the step.
