Mathematical induction

Printable View

July 14th 2012, 11:29 PM
pirateboy

Mathematical induction

I have a two quick questions on mathematical induction. I'm new to it, so my answers seem a little shaky. I wanted to see what some of the you guys thought.

Question 1

We're asked to prove using mathematical induction that for all natural numbers $n$ ,
$\frac{1}{2!} + \frac{2}{3!}+\dots+\frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!}$

Proof (?):

Let $k\in\mathbb{N}$

1. Base case: $k=3$ :

$\begin{align*} \frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!}&=\frac{1}{2}+\frac{2}{6}+\frac{3}{24} \\&=\frac{23}{24}\\&=1-\frac{1}{(3+1)!}\end{align*}$
CHECK

2. Assume $\forall k\in\mathbb{N}$ ,
$\frac{1}{2!} + \frac{2}{3!}+\dots+\frac{k}{(k+1)!} = 1 - \frac{1}{(k+1)!}$ .

Then,
$\begin{align*}\frac{1}{2!} + \frac{2}{3!}+\dots+\frac{k}{(k+1)!} + \frac{k+1}{(k+2)} &= 1 - \frac{1}{(k+1)!} + \frac{1}{(k+2)!}\\&=1 - \frac{1}{(k+1)!}\left(\frac{k+2}{k+2}\right) + \frac{k+1}{(k+2)!}\\&=1 - \frac{k+2}{(k+2)!} + \frac{k+1}{(k+2)!}\\&=1-\frac{1}{(k+2)!}\end{align*}$

3. Thus, by P.M.I. blah blah QED.

Is this legit? It just seems strange to me since I'm working completely on the right side. Yet any other way I try to attempt seems to lead me down some crazy algebra path (I could very well be doing it wrong).

Question 2
Use generalized PMI principles of mathematical induction to prove
$n!>3n\quad\text{for}\quad n\geq 4$

Proof(?):
First, we know that since we're taking a factorial that n must be an integer (this was not originally given to us, so I guess it's implied?).

Let $k\in\mathbb{Z},\quad k\geq 4$
(I guess that since k is greater than 4, I might rotate that Z pi radians and define k as a natural number?)

1. Base case: k = 4

$4!=24>3\cdot4 = 12$

Good.

2. Mathematical induction:
Assume that for some integer $k\geq 4$ that $k!>3k$

Note,
$3(k+1)=3k+3>3k$

Also note,
$k!\geq k(3!)>3(k+1)=3k+3$

And
$(k+1)!>k!$
(since k is always positive.)

So,
$(k+1)!>k!>3(k+1)>3k$

3. by general PMI, i'm done?

Again, this feels a bit shaky to me. Perhaps because I dealt with so many pieces individually before putting it all back together.

So again, my question: Am I using mathematical induction properly here? Do my proofs prove what they are supposed to?
July 15th 2012, 02:33 AM
Prove It

Re: Mathematical induction

Wouldn't the base case be k = 1?
July 15th 2012, 12:56 PM
tom@ballooncalculus

Re: Mathematical induction

Quote:

Originally Posted by pirateboy

1. Base case: $k=3$ :

Use k = 1 as Prove It said... I can see why it might look like that was out of the question, but... the formula tells you you're done as soon as you've written a term equal to

$\frac{n}{(n+1)!}$ ... and that's the case after the first term!

Quote:

Originally Posted by pirateboy

2. Assume $\forall k\in\mathbb{N}$ ,

Not quite - you're assuming the formula true for some (any) particular k.

Then you're ok.

Quote:

Originally Posted by pirateboy

Is this legit? It just seems strange to me since I'm working completely on the right side.

To get a handle on why your first proof is fine (... and the other one not) you need to meditate a little bit on what the 'blah blah' part is actually saying...

http://www.ballooncalculus.org/draw/misc/inducb.png

So the body of your proof must show that 'true for k+1' follows inevitably from 'true for k'. So you need to be conscious of making a chain of sentences linked by 'implies' or 'therefore'.

Not necessarily a chain of expressions linked by equals signs. (Though each sentence may well be such a chain.)

Notice I've inserted one expression directly after the point where you say 'Then'. I wouldn't bother highlight this change except it bears on what I was just saying. Makes it clearer (though only slightly) that you are beginning a chain of expressions that says the original formula is true for k + 1.

http://www.ballooncalculus.org/draw/misc/induc2.png

Quote:

Originally Posted by pirateboy

Note,
$3(k+1)=3k+3>3k$

Also note,
$k!\geq k(3!)>3(k+1)=3k+3$

And
$(k+1)!>k!$
(since k is always positive.)

So,
$(k+1)!>k!>3(k+1)>3k$

3. by general PMI, i'm done?

Again, this feels a bit shaky to me. Perhaps because I dealt with so many pieces individually before putting it all back together.

Well, the way it has to fit together is in a chain of inevitable consequences starting just from $k! > 3k$ .

Your likely choice of a first step forward from that would, I guess, be $k! > k(3!)$ . Which is obviously true... but doesn't actually follow! At least not directly. Here's a chain that works...

http://www.ballooncalculus.org/draw/misc/induc.png