Induction is the only way?

Question

Are there any statements that are true and can only be proved by induction?

(In most of the proofs I saw the induction proof shed some light on another way of proving a statement e.g. with divisibility problems, after solving it by induction you can guess how you should factor the original expression to get the result directly)

Answer 1

In set theory the set $\omega$ of natural numbers is constructed on base of the axiom of infinity. This as the smallest set that contains $\varnothing$ as element and is closed under the operation $a\mapsto a\cup\{a\}$.

After that several properties of natural numbers are proved by induction. For instance the fact that all natural numbers are transitive sets. This by showing that the set $b:=\{n\in\omega\mid n\text{ is transitive}\}$ also contains $\varnothing$ as element and is closed under the operation $a\mapsto a\cup\{a\}$ (induction).

Then $\omega\subseteq b\subseteq\omega$ or equivalently $b=\omega$, wich means that every $n\in\omega$ is transitive.

I don't think there is a way to avoid induction here.

Answer 2

Saying something cannot be proven by any other means but induction is quite a bold statement, and I am not capable of giving it. It is also not an entirely well defined statement, unless you formally define all your axioms (one of which is induction) and then say

"which statements cannot be proven if I remove induction from my set of axioms?"

But I think that's not your question and that your question is more about the proofs you meet during the first years of studying math.

In that case, I would say that technically speaking, many proofs cannot be performed without at least implicitly using induction. For example, if I tell you I have a sequence $\{a_n\}_{n=0}^\infty$ defined as

• $a_0=3$,
• $a_n = a_{n-1} + 3$ for all $n\geq 1$

then I see no way of getting around induction if you want to prove that $a_n$ is divisible by $3$ for all $n$. For example, you may say

Oh that's easy, you can see that $a_n = 3n + 3$ for all $n$, so since $a_n = 3k$ for some $k$, it is divisible by $3$!

But then, how would you prove that $a_n = 3n + 3$ is true without using induction?