# Mathematical induction usage

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.

-
One could certainly proceed to establish your particular example sans induction, if one notices that the fourth and higher differences vanish... –  Ｊ. Ｍ. Oct 23 '11 at 14:04

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.

-
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