You are Here: Home

# Proof by mathematical induction Tweet

Maths and statistics discussion, revision, exam and homework help.

Announcements Posted on
1. Proof by mathematical induction
Just can't get into proof by mathematical induction

MS221 2009 Q16 c

Prove 2^n < n! for n greater or equal to 5 (4 marks)

First solve for p(5) done & true,

So presume p(k) true

For for p(k+1) I would say

2k+1 = (k+1)!
thus
2x2k = k!(k+1)

then not sure where to go.. think i'd get 2 out of the 4 marks at least ...
2. Re: Proof by mathematical induction
The idea is to extend what we'd do in a particular case,
for example, 2^5 < 5!, so 2*2^5< 5! * 2 < 5! * 6, 2^6 < 6!

For induction we write a general argument.

Edit: And of course show that it's true for some case, important!
As a side note, why was there all those nonsense words we were to write at A level? It was a good 3 lines of needless rubbish, not seen it at uni, reminds me of mixed numbers.
Last edited by Allofthem; 14-06-2012 at 20:00.
3. Re: Proof by mathematical induction

but

so
4. Re: Proof by mathematical induction
Using your notation, I'd write something like:

We know the statement P(5) is true. Now for k >= 5, suppose P(k) is true. We WTS P(k+1) must also be true.

2^k+1 = 2 * 2^k < 2 * k! as P(k) is true
< (k+1) * k! as 2 < k
= (k+1)!

so P(k+1) is true. So we have P(5) true, and for k >= 5, P(k) true implies P(k+1) true; hence by induction, P(n) is true for all n >= 5.