The reason proof by induction works is because of the well-ordering principle (WOP) of the natural numbers. The well-ordering principle says any nonempty subset of the natural numbers has a least element. It turns out that WOP is logically equvalent to the principle of mathematical induction (PMI). This is fairly straightforward to prove as follows:
$WOP\leftarrow PMI$ Suppose $S$ has no minimal element. Then $ n = 1 \notin S$, because otherwise $n$ would be minimal. Similarly $n = 2 \notin S$, because then $2$ would be minimal, since $n = 1$ is not in $S$. Suppose none of $1, 2, \cdots, n$ is in $S$. Then $n+1 \notin S$, because otherwise it would be minimal. Then by induction $S%$ is empty, a contradiction.
$WOP\leftarrow PMI$ Suppose $P(1)$ is true, and $P(n+1)$ is true whenever $P(n)$ is true. If $P(k)$ is not true for all integers, then let $S$ be the non-empty set of $k$ for which $P(k)$ is not true. By well-ordering $S$ has a least element, which cannot be $k = 1$. But then $P(k-1)$ is true, and so $P(k)$ is true, a contradiction.
So clearly WOP is true iff PMI is true. A lot of teachers don't like going through this in basic rigorous mathematics courses, which to me is a big mistake. Students need to understand why induction works,it's a critical method of proof.