Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a question on Mathematical Induction.
Ok, when we are presented let's take a concrete example, with a sum of finite numbers and say we want to prove a result, e.g. that:

$$ S_n = 1 + 4 + 9 + 16 +\cdots + n^2 = \frac{n(n+1)(2n+1)}{6} $$

for integers $n\geq 1$

we can use mathematical induction to prove it.

But did the result to be proven came up from induction in the first place?
Or induction is just a tool to prove an outcome, fast, that we originally concluded by other means?
Note: The $S_n$ above is an example. My question is generic on induction principle.

Thank you.

share|improve this question
    
One could certainly proceed to establish your particular example sans induction, if one notices that the fourth and higher differences vanish... –  J. M. Oct 23 '11 at 14:04

1 Answer 1

up vote 7 down vote accepted

It depends on the theorem and on the mathematician, of course.

Sometimes it's obvious when looking at a problem that induction needs to be used, and what the inductive hypothesis needs to be. For example, consider the problem of proving that every integer greater than 1 has a prime divisor. I notice that every such integer must either be prime, or divisible by a smaller integer, also greater than one; this suggests to me that I can use (strong) induction to formalize this breaking of the problem into smaller pieces.

For formulas like the one you posted, though, I would almost never immediately jump into a proof by induction. I just wouldn't know where to begin. Instead, I would try some numerical examples, and see if I can work out a formula or pattern. Looking at the sequence 1, 5, 14, $\ldots$ I might start taking finite differences and notice that the terms are given by a cubic polynomial. I would then solve for the coefficients, which would give me the formula: only after I'd convinced myself that the formula worked for small values of $n$ would I start thinking about how to prove it correct using induction.

share|improve this answer
    
To sum it all up: Induction is not a method to invent a formula or "see" a theorem, but a method of proof of a good conjecture. –  Christian Blatter Oct 23 '11 at 17:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.