# Mathematical induction

• Jul 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 $\displaystyle n$,
$\displaystyle \frac{1}{2!} + \frac{2}{3!}+\dots+\frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!}$

Proof (?):

Let $\displaystyle k\in\mathbb{N}$

1. Base case: $\displaystyle k=3$:

\displaystyle \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 $\displaystyle \forall k\in\mathbb{N}$,
$\displaystyle \frac{1}{2!} + \frac{2}{3!}+\dots+\frac{k}{(k+1)!} = 1 - \frac{1}{(k+1)!}$.

Then,
\displaystyle \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
$\displaystyle 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 $\displaystyle 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

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

Good.

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

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

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

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

So,
$\displaystyle (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?
• Jul 15th 2012, 02:33 AM
Prove It
Re: Mathematical induction
Wouldn't the base case be k = 1?
• Jul 15th 2012, 12:56 PM
tom@ballooncalculus
Re: Mathematical induction
Quote:

Originally Posted by pirateboy
1. Base case: $\displaystyle 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

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

Quote:

Originally Posted by pirateboy
2. Assume $\displaystyle \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,
$\displaystyle 3(k+1)=3k+3>3k$

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

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

So,
$\displaystyle (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 $\displaystyle k! > 3k$.

Your likely choice of a first step forward from that would, I guess, be $\displaystyle 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