Mathematica Is induction just a lazy alternative to real proofs?

[hypermonkey2]

It seems to me that sometimes mathematical induction can be a lazy alternative to a real proof. I am bothered by the fact that induction does not tell you why something works, nor can it help in the actual derivation of formulae. Am i right in throwing it away so quickly? It just seems inelegant.

Bobo

 

[shmoe]

It seems to me that sometimes mathematical induction can be a lazy alternative to a real proof.

Induction is a perfectly valid technique.

I am bothered by the fact that induction does not tell you why something works, nor can it help in the actual derivation of formulae.

What are you looking for with the "why something works"? To me an induction proof (or any other proof) will answer the question of why a statement is true.

Am i right in throwing it away so quickly? It just seems inelegant.

Elegant is a subjective term, but there are many elegant induction proofs in my opinion. There are countless examples, but the first pretty one that comes to mind is proving that all integers have a prime factorization. You can also prove there are infinitely many primes in an induction type of proof, this version will also lead to crude bounds on the nth prime.

I could go on for pages about the pretty uses of induction. I suspect you've mostly been subjected to simple statements like formulas for the sum of the first n integers, which could also be proven directly. Look around, it's not hard to find less simplistic uses.

 

[hypermonkey2]

You bring a valid argument with the inductive proof of the interminable list of primes. I suppose i am vexed by inductive proofs say, the following:

Prove by induction that N^3 - N is always a multiple of 6 for N>2. \

The inductive proof of this is a bit laborious and inefficient. Yes, we do prove that the formula works, but we do not see why. The proof of this that I much prefer is the following.

N^3-N= N(N-1)(N+1)

we see that it is just the product of 3 consecutive numbers no? it suddenly makes more sense that it must be divisible by 6.(since 1 in 3 numbers are divisible by 3, and 1 in 2 are even).

I suppose its more vexing for trivial examples, and i also can suppose that induction can be powerful for much more complex proofs.

 

[shmoe]

Yes, we do prove that the formula works, but we do not see why.

Sure we do. In the course of the induction proof you'll see going from N^3-N to (N+1)^3-(N+1) involves adding 3N^2+3N, which is always divisible by 6 by an even/odd argument. So the induction tells you that any two numbers in the sequence 1^3-1, 2^3-2, 3^3-3, ... differ by a multiple of 6. Hence if one of them (your "base case") is divisible by 6 they all are. What more do you want for an answer to "why"?

The demand to answer this via induction is for pedagogical reasons. It's to give you another example of where you can apply induction and gives you practive applying it to a 'trivial' example to prepare you for more complicated uses. Also, it never hurts to have more than one way of proving a statement, the alternates may supply different insights (as in the bounds on the nth prime)

If you want more non-trivial examples, any graphy theory text will be filled with them. You might see induction on the number of edges a graph has, the number of vertices, it's girth, or other parameters that you might not have expected. Sometimes it will be possible to convert to a non-inductive proof, but sometimes induction will be the slickist approach (slick being subjective of course).