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.
 A: 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.
