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

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?

  • $\begingroup$ are you trying to prove $n^2 \geq 2n$ or $2^n \geq 2n$? $\endgroup$ – Saurabh Jul 13 '12 at 5:09
  • 1
    $\begingroup$ @aerotwelve I've tried to improve your post using TeX (for better readability). For some basic information about writing math at this site see here or here. $\endgroup$ – Martin Sleziak Jul 13 '12 at 5:13
  • $\begingroup$ @SaurabhHota Apologies, I fixed this. Edited. $\endgroup$ – aerotwelve Jul 13 '12 at 5:14
  • $\begingroup$ @aerotwelve: When you edit the question such that something in one of the existing answers no longer makes sense, it's good style to indicate that (e.g. by marking it by "[ Edit ]" or something like that), not just in a comment (which not everyone reads) but in the question itself, where the change occurred. Otherwise good answers may appear wrong or misguided. $\endgroup$ – joriki Jul 13 '12 at 5:18
  • $\begingroup$ @joriki -- that was a mistake on my part. The question is back to the way it should be. Sorry about the confusion, it's been a long night. $\endgroup$ – aerotwelve Jul 13 '12 at 5:22

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)$.


$(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^+$.

  • 1
    $\begingroup$ Could you please elaborate on how you invoke the IH? I understand expanding the left [(k+1)2=k2+2k+1], but I dont understand where the third inequality comes into play. $\endgroup$ – aerotwelve Jul 13 '12 at 5:21
  • 1
    $\begingroup$ Induction hypothesis is $k^2\geq 2k$ (as given in your problem).Now add $2k+1$ to both sides of this inequality which gives $k^2+2k+1\geq 2k+2k+1$ which is in fact $=4k+1$. As $k\geq 1\implies 2k\geq 2\implies 2k+1\geq 3\implies (2k+2k+1=4k+1)\geq 2k+3$. From inequality $k^2+2k+1\geq 2k+2k+1 \geq 2k+3 \gt 2k+2\implies (k+1)^2\geq 2(k+1)$. $\endgroup$ – Aang Jul 13 '12 at 5:28

We have to prove $2^n \geq 2n$ for $n>1$
$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).$

  • $\begingroup$ Why is there a strict inequality when you want to use the IH? $\endgroup$ – Volker Stolz Nov 19 '15 at 9:46
  • $\begingroup$ Error. Make that $(k+1)^2 \ge 2(k+1)$ $\endgroup$ – steven gregory Oct 28 '16 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.