21
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ are you trying to prove $n^2 \geq 2n$ or $2^n \geq 2n$? $\endgroup$
    – Saurabh
    Jul 13, 2012 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$ Jul 13, 2012 at 5:13
  • $\begingroup$ @SaurabhHota Apologies, I fixed this. Edited. $\endgroup$
    – aerotwelve
    Jul 13, 2012 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, 2012 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, 2012 at 5:22

2 Answers 2

13
$\begingroup$

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

$\endgroup$
2
  • 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, 2012 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, 2012 at 5:28
10
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Why is there a strict inequality when you want to use the IH? $\endgroup$ Nov 19, 2015 at 9:46
  • $\begingroup$ Error. Make that $(k+1)^2 \ge 2(k+1)$ $\endgroup$ Oct 28, 2016 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.