2
$\begingroup$

I often see proofs, that claim to be by induction, but where the variable we induct on doesn't take value is $\mathbb{N}$ but only in some set $\{1,\ldots,m\}$.

Imagine for example that we have to prove an equality that encompasses $n$ variables on each side, where $n$ can only range through $n\in\{1,\ldots,m\}$ (imagine that for $n>m$ the function relating the variables on one of the sides isn't welldefined): For $n=1$ imagine that the equality is easy to prove by manipulating the variables algebraically and that for some $n\in\{1,\ldots,m\}$ we can also show the equation holds provided it holds for $n\in\{1,\ldots,n-1\}$. Then we have proved the equation for every $n\in\{1,\ldots,m\}$, but does this qualify as a proof by induction ?

(Correct me if I'm wrong: If the equation were indeed definable and true for every $n\in\mathbb{N}$ we could - although we are only interested in the case $n\in\{1,\ldots,m\}$ - "extend" it to $\mathbb{N}$ and then use "normal" induction to prove it holds for every $n\in \mathbb{N}$, since then it would also hold for $n\in\{1,\ldots,m\}$ .)

  • 0
    Could you be thinking about the principle of strong (or complete) induction? See: http://en.wikipedia.org/wiki/Mathematical_induction#Complete_induction2013-01-02

2 Answers 2

5

If the statement in question really does not "work" if $n>m$, then necessarily the induction step $n\to n+1$ at least somewhere uses that $n. You may view this as actually proving by induction $\tag1\forall n\in \mathbb N\colon (n>m\lor \phi(m,n))$ That is, you first show $\tag2\phi(m,1)$ (which of course implies $1>m\lor \phi(m,1)$) and then show $\tag3(n>m\lor \phi(m,n))\Rightarrow (n+1>m\lor \phi(m,n+1)),$ where you can more or less ignore the trivial case $n\ge m$. Of course $(2)$ and $(3)$ establish a perfectly valid proof of $(1)$ by induction on $n$.

2

This "form" of induction is called finite or finitistic induction. If we want to prove a property $p$ holds $\forall x\in A$ where $A$ is a finite set $A=\left\{x_1,x_2,...,x_n\right\}$, then we just have to check if $p(x_1),p(x_2),...,p(x_n)$ are true. If $A=\left\{0,1,...,m\right\}$ then we can also perform finite induction.

As you said, finite induction is much more weaker and restricted compared to infinite induction. In fact if we want to prove a property holds for a finite number of natural numbers and we can prove that it holds in $\mathbb{N}$ by (infinite) induction, then it holds automatically for these numbers as well.

Use of finite induction is not neccessary to prove a property holds for a finite set, as we can check if every element of a finite set has a certain property. Infinite induction however, is a very important axiom in Peano Arithmetic and in many cases necessary to prove properties of all natural numbers.