Re: Mathematical induction

Wouldn't the base case be k = 1?

Re: Mathematical induction

Quote:

Originally Posted by

**pirateboy** 1. Base case:

:

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

... and that's the case after the first term!

Quote:

Originally Posted by

**pirateboy** 2. Assume

,

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,

Also note,

And

(since k is always positive.)

So,

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 .

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