Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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\}$ .)

share|improve this question
    
Could you be thinking about the principle of strong (or complete) induction? See: en.wikipedia.org/wiki/Mathematical_induction#Complete_induction –  Dan Christensen Jan 2 '13 at 5:15
add comment

2 Answers

up vote 5 down vote accepted

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<m$. 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$.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.