Re: Mathematical induction

Wouldn't the base case be k = 1?

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