Mathematical induction

**pirateboy** · July 14th 2012, 11:29 PM

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?

**Prove It** · July 15th 2012, 02:33 AM

Wouldn't the base case be k = 1?

**tom@ballooncalculus** · July 15th 2012, 12:56 PM

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!

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.

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

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.

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

Thread: Mathematical induction

LinkBack

Thread Tools

Display