Proving Inequalities using Induction

I'm pretty new to writing proofs. I've recently been trying to tackle proofs by induction. I'm having a hard time applying my knowledge of how induction works to other types of problems (divisibility, inequalities, etc). I've been checking out the other induction questions on this website, but they either move too fast or don't explain their reasoning behind their steps enough and I end up not being able to follow the logic.

I do understand how to tackle a problem which involves a summation. This is the one I just did (the classic "little gauss" proof):

Prove $1+2+3+\dots+n = n(n+1)/2$

I. Basis
$1=(1+1)/2$
$1=1$

II. Induction

Assume the expression holds for an arbitrary $n=k$ such that $1+2+3+\dots+k = k(k+1)/2$

Show that the expression holds for $n=k+1$ $1+2+3+...+n+k+(k+1) = k+1[(k+1)+1]/2$

And this is done mainly by observing that we already have a formula for 1 through k on the LHS, so the equation can be rewritten as

$k(k+1)/2 + (k+1) = k+1[(k+1)+1]/2$
NOTE: I believe this is using the inductive hypothesis. Please correct me if I'm wrong.

Anyway, finding common denominators on the left hand side and distributing on the right, you eventually show that it's true. This (so far) has worked for every proof I've attempted that involves a summation on the left hand side.

Now, I start losing it when the format changes. For example, this inequality proof I'm trying to write. I'll post what I have here:

$n^2 \ge 2n$ for all $n>1$

I. Basis
$2^{2} \ge 2(2)$
$4 \ge 4$

II. Induction

Assume the inequality holds for an arbitrary $n=k$, such that
$k^2 \ge 2(k)$

Show that the expression holds for $n=k+1$ such that
$(k+1)^2 \ge 2(k+1)$

This is where I get lost andI know I'm supposed to invoke the IH somewhere in the expression. But unlike the summation problem earlier, I'm not sure where to begin. Could anyone point me in the right direction?

Solution 1:

Induction hypothesis is not $2^k\geq 2k$ but $k^2\geq 2k$. Then, for $P(k+1)$, we have to prove $(k+1)^2\geq 2(k+1)$.

Proof:

$(k+1)^2=k^2+2k+1$ but $k^2 \geq 2k$ (by IH) $\implies k^2+2k+1\geq (2k+2k+1=4k+1)\geq 2k+2$ as $k\geq 1\implies (k+1)^2\geq 2(k+1)$. Hence ,$P(k+1)$ is true whenever $P(k)$ is true. Since $P(1)$ is true $\implies P(n)$ is true $\forall n\in \Bbb Z^+$.

Solution 2:

We have to prove $2^n \geq 2n$ for $n>1$
Basis:
$n=2$ which satisfies the above relation.

Induction hypothesis:
Here we assume that the relation is true for some $k$ i.e. $P(k)\colon 2^k \geq2k$.

Now we have to prove that the relation also holds for $k+1$ by using the induction hypothesis. This means that we have to prove $$P(k+1)\colon 2^{k+1} \geq 2(k+1)$$ So the general strategy is to reduce the expressions in $P(k+1)$ to terms of $P(k)$. So,
$$2^{k+1}=2^k\cdot 2=2^k+2^k \geq2^k+2 \quad \quad \{\text{Since }n>1\}$$ Now we will use induction hypothesis that $2^k\ge 2k$ which gives us $$ 2^{k+1}\geq 2^k+2 \geq 2k+2 =2(k+1)$$ which was required. Hence we have proved $P(k+1).$