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?