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?
Best Answer
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^+$.