When do we use hidden induction?

Question

If I'm correct, hidden induction is when we use something along the lines of "etc..." in a proof by induction. Are there any examples of when this would be appropriate (or when it's not appropriate but used anyway)?

Answer 1

It's ubiquitous in inductive proofs by telescopy, e.g. multiplicative telescopic cancellation

$\qquad\qquad\, \displaystyle (x-1)(x+1)(x^{\large 2}\!+1)(x^{\large 4}\!+1)\qquad\! \cdots\qquad (x^{\large 2^{\rm N}}\!+\,1)$

$\qquad\ \ \ = \ \displaystyle \frac{\color{#0a0}{x-1}}{\color{#90f}1} \frac{\color{brown}{x^{\large 2}-1}}{\color{#0a0}{x-1}}\frac{\color{royalblue}{x^{\large 4}-1}}{\color{brown}{x^{\large 2}-1}}\frac{\phantom{f(3)}}{\color{royalblue}{x^{\large 4}-1}}\, \cdots\, \frac{\color{#c00}{\large x^{\large 2^{\rm N}}\!-1}}{\phantom{f(b)}}\frac{x^{\large 2^{\large \rm N+1}}\!-1}{\color{#c00}{x^{\large \rm 2^N}\!-1}} \,=\, \frac{x^{\large 2^{\rm N+1}}-1}{\color{#90f}1} $

As to your question about rigor, informal proofs like the above can be mechanically rewritten into a rigorous inductive proof by anyone who is proficient with telescopic induction. But that is not necessarily the case for someone who is not (esp. for hairer problems where the telescopic cancellation is not so obvious).

Thus typically it depends upon the context whether or not such informal proofs will be accepted as complete. If we are in a context where it is assumed that telescopic induction is known then such informal proofs may indeed be deemed acceptable. Otherwise more needs to be said to convince the reader that you know how to complete the proof into standard inductive form.

Similar remarks hold for other common forms of inductive proofs. For example, many of my posts illustrate how the use of modular arithmetic (congruences) allows us to transform many inductive divisibility problems into a trivial induction such as $\, x\equiv 1\,\Rightarrow\, x^n\equiv 1,\,$ a consequence of the Congruence Power Rule (which has an obvious simple inductive proof). In a number theoretical context you would not be expected to give a rigorous inductive proof of the concluding inference, essentially $\,1^n\equiv 1\,$ (or, similarly $(-1)^{2n}\equiv 1).$ But in other contexts you would be expected to be more explicit, esp, if you are working without the simplifying language of congruences, so the innate algebraic structure may be much more obfuscated, greatly complicating the intuition needed to devise the inductive step. For example see this post where I explain how a divisibility inductive proof that is typically pulled out of a hat like magic, is nothing but a special case of the Congruence Product Rule, and the inductive proof becomes obvious from the algebraic perspective.

Answer 2

Here is an example. Suppose that $A$ is a diagonalizable matrix, i.e. $A=P^{-1}DP$ where $D$ is some diagonal matrix. Then $A^k=P^{-1}D^kP$. Indeed, we have that $$A^k=(P^{-1}DP)^k=P^{-1}D(PP^{-1})D(PP^{-1})\dots (PP^{-1})DP=P^{-1}D^kP.$$ Here we actually used induction in the dots. There are many examples of this fashion.

Answer 3

First, here is an example of when this works. Let $X$ and $Y$ be Hausdorff spaces. This implies $X\times Y$ with the product topology is Hausdorff. Therefore any finite product of Hausdorff spaces is Hausdorff. The "hidden induction" is the idea that $X\times Y$ is a Hausdorff space, which implies any Hausdorff space times $X\times Y$ is also Hausdorff. This argument can continue for any finite number of spaces.

An example of when you can't use this argument is the proof of $\Sigma_{i=1}^n=\frac{n(n-1)}{2}$. Here, showing the truth for $n=1$ does not make it immediately clear that the rest follows by induction.

It was appropriate to use this in the first problem as it was clear that it follows. But the second problem isn't as obvious. It is like a lot of other problems in mathematics; the mathematician must develop an intuition for when something is obvious enough to not require an explicit explanation (e.g. $2*1=2$).

Answer 4

Hidden induction happens a lot in cases where you go backwards from $n$ to $1$, using some kind of reduction argument. For example, the proof that every number can be written as a product of primes:

Let $n$ be some number. If it's prime, then we're done. Otherwise it can be written as $ab$, with $a, b < n$. Again, if both $a$ or $b$ are prime, we're done, otherwise they can be broken up in the same way. Since the factors are getting smaller and smaller, this process must stop eventually, but the only way it can stop is if one of all of the numbers involved are prime.

Induction serves to tighten up the structure of the argument, replacing a vague "this process must stop" with an explicit invocation of an axiom:

Suppose every number less than $n$ can be written as a product of primes. If $n$ is prime, we're done. Otherwise, $n=ab$ with $a, b < n$, so $a$ and $b$ can be written as products of primes. Therefore $n$ can be written as a product of primes.