h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

does anyone have a clue why proof by induction works? look at the way it goes:

1. the property is true of the smallest integer to which it is applicable (the basis)
2. assume that it works for all integers in [basis,n)
3. from 2, prove that it works for n
4. therefore it works for all n

the bug here is, the proof of the property n is supposed to show that it works for all n, ASSUMING it works for all integers till n-1. how does the proof actually show that the assumption is justified? in other words, the proof-by-induction procedure is supposed to assume something, and then declare that the proof of the property means that the assumption is valid!!

something's circular here, and i can't put my finger on it. i am guessing that the proof by induction process is dependent on some property of the integers: some form of closure, perhaps. would it be valid for a property that can be mapped to an uncountably infinite set, say the reals?

If a proof by induction has been done (according to your four points), the following chain of logic is made possible:

1. It's true for the basis (1 mostly)
2. From this it follows that it's true for basis+1.
3. From 1.+2. it follows that it's true for basis+2.
etc.

So it's true for all integers>=basis. And that is what was wanted originally.

Or, to answer the core problem that you have directly: The proof is infinitely long, only written in a concise form. The assumption that the theorem is valid till n-1 is needed at a stage when -- by using the steps above -- this is indeed proved already.

hey, THAT is evident. what is not evident, and what i just figured is that the proof step must involve no transformations that are not applicable to the basis. in other words, the proof step and the basis must be consistent.

as an illustration, consider the famous "proof" that all horses are of the same colour (you can find this in many books, notably Knuth - The Art of Computer Programming, Vol 1.).

> the proof step must involve no
> transformations that are not
> applicable to the basis

Yes, but that's obvious, isn't it?

After all, it says "*From* *this* it follows that it's true for basis+1". This is pretty unambiguous.