The well-trodden natural induction is just one type of induction. There are other kinds as well.
When we prove something about objects, it is useful to first ask: how do these objects come into being?
Consider the following grammar:
\[S ::= \texttt{x} \mid \texttt{a}S\texttt{a} \mid \texttt{b}S\texttt{b}.\]This grammar generates objects such as:
\[\texttt{x},\quad \texttt{axa},\quad \texttt{bxb},\quad \texttt{aaxaa},\quad \texttt{abxba},\quad \texttt{bbxbb}.\]The grammar is not merely a way of describing some strings. It is the set of generative rules for the entire collection. More precisely, $S$ is the smallest set of strings closed under these rules.
It says the following:
\[\frac{}{\texttt{x} \in S} \qquad \frac{s \in S}{\texttt{a}s\texttt{a} \in S} \qquad \frac{s \in S}{\texttt{b}s\texttt{b} \in S}.\]So every object in this set is either the base object $\texttt{x}$, or it is obtained by taking an already-generated object and wrapping it with $\texttt{a}$ on both sides, or wrapping it with $\texttt{b}$ on both sides.
Now suppose we want to prove something about every object in this set. Let the property be called $P$. We could try to inspect the objects one by one, but that is not possible. There are infinitely many of them. The useful thing is not to look at the objects separately, but to look at the rules that generate them. If we can prove that $P$ is true for the base object, and if we can prove that every generative rule preserves $P$, then every generated object must satisfy $P$.
So the proof has two parts. First, we prove the base case:
\[P(\texttt{x})\]Then we prove that the construction rules preserve the property:
\[P(s) \implies P(\texttt{a}s\texttt{a}),\] \[P(s) \implies P(\texttt{b}s\texttt{b}).\]This is induction. The proof follows the construction of the objects.
As a concrete example, let us prove that every string generated by this grammar is a palindrome. The base case is easy:
\[\operatorname{Pal}(\texttt{x}).\]The base string is a palindrome. For the inductive step, assume that some generated string is a palindrome:
\[\operatorname{Pal}(s).\]This is the inductive assumption. If this is true, then wrapping the string with the same symbol on both sides preserves the property:
\[\operatorname{Pal}(s) \implies \operatorname{Pal}(\texttt{a}s\texttt{a}),\] \[\operatorname{Pal}(s) \implies \operatorname{Pal}(\texttt{b}s\texttt{b}).\]So the property of being a palindrome is preserved by every rule of the grammar. Therefore, every string generated by
\[S ::= \texttt{x} \mid \texttt{a}S\texttt{a} \mid \texttt{b}S\texttt{b}\]is a palindrome.
This is the main idea behind induction: prove the property at the beginning, and prove that the rules for making new objects preserve the property. Natural number induction is just one instance of this idea.
The natural numbers can be seen as being generated by rules:
\[\mathbb{N} ::= 1 \mid \operatorname{succ}(\mathbb{N})\]This says:
\[\frac{}{1 \in \mathbb{N}} \qquad \frac{n \in \mathbb{N}}{\operatorname{succ}(n) \in \mathbb{N}}.\]So to prove a property for all natural numbers, we again follow the generative rules. We prove the base case:
\[P(1),\]and then prove the successor step:
\[P(n) \implies P(\operatorname{succ}(n)).\]This works because we have covered every way in which a natural number can come into being. There are other inductions too, such as structural induction.
For example, binary trees may be generated by:
\[\operatorname{Tree} ::= \operatorname{Leaf} \mid \operatorname{Node}(\operatorname{Tree}, \operatorname{Tree}).\]This says:
\[\frac{}{\operatorname{Leaf} \in \operatorname{Tree}} \qquad \frac{t_1 \in \operatorname{Tree} \quad t_2 \in \operatorname{Tree}} {\operatorname{Node}(t_1,t_2) \in \operatorname{Tree}}.\]So if we want to prove that every tree has some property $P$, we again prove the property by following the way trees are generated. We prove the base case:
\[P(\operatorname{Leaf}).\]Then we prove the node case:
\[P(t_1) \land P(t_2) \implies P(\operatorname{Node}(t_1,t_2)).\]Again, the proof mirrors the generative structure of the objects. The important point is that induction is not fundamentally about numbers. It is about generated objects. Whenever a collection is built from some base objects and some construction rules, an inductive proof follows the same shape:
\[\text{base objects satisfy } P \qquad \text{and} \qquad \text{construction rules preserve } P.\]Natural induction is only the most familiar case. The deeper idea is that to prove something about all objects in a generated set, we prove the property for the base objects and then show that the generating rules preserve it.