Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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. I 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?

share|improve this question
    
are you trying to prove $n^2 \geq 2n$ or $2^n \geq 2n$? –  Saurabh Jul 13 '12 at 5:09
1  
@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. –  Martin Sleziak Jul 13 '12 at 5:13
    
@SaurabhHota Apologies, I fixed this. Edited. –  aerotwelve Jul 13 '12 at 5:14
    
@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. –  joriki Jul 13 '12 at 5:18
    
@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. –  aerotwelve Jul 13 '12 at 5:22
show 1 more comment

2 Answers 2

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

share|improve this answer
    
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. –  aerotwelve Jul 13 '12 at 5:21
    
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)$. –  Aang Jul 13 '12 at 5:28
add comment

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):2^k \geq2k$.

Now we have to prove that the relation also holds for $k+1$ by using induction hypothesis. that means we have to prove $$P(k+1):2^{k+1} \geq 2(k+1)$$ So the general strategy is to reduce the expression in $P(k+1)$ terms of $P(k)$.So,
$$2^{k+1}=2^k.2=2^k+2^k \geq2^k+2 \quad \quad \{\text{Since }n>1\}$$ Now we will use induction hypothesis that $2^k>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).$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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