Applications of mathematical induction

I often see mathematical induction used to verify proofs. For example the formula for the sum of all integers up to an n. Unfortunately this says nothing about how the formula was found in the first place, and if mathematical induction played a role in the finding.

I then thought about Euclid's proof of the infinite amount of prime numbers. Induction seems to play an essential role here, but again, how do you come to the idea of multiplying all known prime numbers so far, adding one, and reasoning about the primality of this number again?

So, what exactly are the applications of mathematical induction? Just for giving alternate, maybe easier, proofs for theorems you already know they are true, and you already proved them in some other way? Or do you guess the theorem and only with induction you can show that it is actually true? Are there examples where induction was used in the first place to find a new theorem?

• Induction is a tool. Like an oven. Understanding how the oven works will allow you to make wonderful meals; but lacking the creativity to design and come up with the recipes is not one of the jobs of the oven, it's the job of the chef. – Asaf Karagila Mar 12 '13 at 10:41
• @AsafKaragila +1 +1 +1 :) – Ittay Weiss Mar 12 '13 at 10:48
• @Ittay: Which sums up to +3 which is the current state of affairs. – Asaf Karagila Mar 12 '13 at 10:51

First, the product of all primes up to $k$, plus $1$ is not necessarily a prime number. Second, what is sometimes called Euclide's proof of the infinitude of primes numbers has two popular versions. One is a proof by contradiction and uses no induction. The other can be stated in the form of an inductive proof.