What does "prove by induction" mean?
What does "Prove by induction" mean? Would you mind giving me an example?
$\endgroup$ 75 Answers
$\begingroup$Proof by induction means that you proof something for all natural numbers by first proving that it is true for $0$, and that if it is true for $n$ (or sometimes, for all numbers up to $n$), then it is true also for $n+1$.
An example:
Proof that $1+2+3+\dots+n = n(n+1)/2$:
For $n=0$, on the left hand side you've got the empty sum, which by definition is $0$. On the right hand side, you've got $0(0+1)/2=0$. So the euqation is true for $n=0$.
Assume that the formula is true for $n$. Then we can prove it for $n+1$ as follows:
By assumption, $1+2+\dots+n+(n+1)=n(n+1)/2 + (n+1)$. But the right hand side is easily calculated to equal $(n+1)((n+1)+1)/2$.
Now since we have proven it for $0$, and for $n+1$ assuming it's true for $n$, we have proven it by induction for all $n$.
The first part is known as induction start, and the second part as induction step.
Now of course you want to know:
Why does it work?
Imagine that you want to know whether it is true for $n=5$. Of course you could just calculate it directly, but assume you've forgotten how to calculate it, and all you remember is that you've proven it for $n=0$ and that if it is true for $n$, then it is true also for $n+1$.
OK, you know it is true for $n=0$.
If it is true for $n=0$, then by the induction step, which you've proven, it is true for $n+1=1$
But if it is true for $n=1$. them by the induction step it is true for $n+1=2$.
But if it is true for $n=2$. them by the induction step it is true for $n+1=3$.
But if it is true for $n=3$. them by the induction step it is true for $n+1=4$.
But if it is true for $n=4$. them by the induction step it is true for $n+1=5$.
Therefore you have proven it for $n=5$.
It is easy to see that this allows you to mechanically formulate a proof for any individual $n$, and thus it is obvious that it must be true for all $n$.
$\endgroup$ 2 $\begingroup$Proof by induction is inherent in the Peano postulates/axioms. If $0$ is in a set $A$ and whenever $n \in A$, the successor $Sn \in A$ then every (non-negative integer) number is in $A$.
This mirrors the base case $0$ and the inductive step from $n$ to $n+1$
Some sets are inductive, and others are not. The natural numbers, non-negative integers, or integers greater than some arbitrary integer $r$ (negative, zero or positive) are all inductive sets.
The fact that Peano had to specify the inductive axiom suggests that it is not quite as obvious as it seems and that your question is non-trivial. There are technical issues of "first order" and "second order" arithmetic in the background. But as in other answers, the principle also seems to be intuitively obvious, and the foundational complexity comes to most people as a surprise.
$\endgroup$ 5 $\begingroup$An example question:
Let $A$, $B$, $C$ be sets. Prove that if $A_1 \subset A_2$, $A_2 \subset A_3$,.....,$A_{n-1} \subset A_n$ then $A_1 \subset A_n$
So if you set out to prove that if $A_1 \subset A_2$ and if $A_2 \subset A_3$. And then $A_1 \subset A_3$. It is then 'inductively' obvious that $A_1 \subset A_n$ as it is true for n=1, 2, 3.
$\endgroup$ $\begingroup$Hint:
Mr @celtschk and Mr @Chris Eagle explain induction proof completely now i give an example about it : $\dfrac{dx^{n}}{dx}=nx^{n-1}$
we know $\dfrac{d (u v) }{dx}=u\dfrac{d v }{dx}+v\dfrac{du }{dx}$ or $(UV) '=U 'V+U V '$
- For $n=1$ clearly it is true
- Assume that the statement is true for $n$ now i prove its true for $n+1$ $$\large{\dfrac{dx^{n+1}}{dx}=\dfrac{d (x x^{n})}{dx}=x^n+x(nx^{n-1})=(n+1)x^{n}}$$
@celtschk's answer is the most appropriate. I am enticed by @markbennet's answer. It looks like Peano definitely had the notion of hereditary class (all successors of $\mu$'s are $\mu$'s with respect to R), or, at least, a precursor of it.
In W&R's principia, Mathematical induction is a particular case of inheritance. If a property is hereditary with respect to a relation R and if a certain member of R's domain possesses such a property, then all the descendants of this member possess this property.
General steps of proof:
Show that a property is hereditary: let $x$ be any member of $R$'s domain, and x has relation R to $y$, i.e. $xRy$, and if $\phi(x)$ implies $\phi(y)$, then $\phi$ is hereditary with respect to $R$.
Find a $w$ such that $w$ is a member of R's domain and $\phi(w)$.
It follows from 1 and 2 that $\phi$ is a property possessed by all of $w$'s descendants with respect to $R$
In the case of mathematical induction, $R$ is the relation $+1$ and R's domain consists of all the numbers that can be reached from $0$ by successive additions of $1$.
Then how do we know this property belongs to all inductive numbers? In PM, inductive numbers are defined as ancestors of $0$ with respect to $+1$ (see ✳120.01). By applying the definition of ancestor(see✳90.01, $x$ is said to be an ancestor of $y$ with respect to $R$ when $x$ belongs to the field of R, and $y$ belongs to every hereditary class to which $x$ belongs), inductive cardinals are those that possess every property possessed by 0 and by the numbers obtained by adding 1 to numbers possessing the property.
Thus, if a property is possessed by 0 and by the numbers obtained by adding 1 to numbers possessing the property, then the property is possessed by all inductive numbers. Hence, mathematical induction, in PM, turns out to be a definition, not a principle.
Mathematical induction adds nothing new to human knowledge about the external world. There is another type of induction, induction by simple enumeration, that does. Induction by simple enumeration is fallacious, unreliable, but it is much more important than its mathematical counterpart, because it leads to new discoveries and it is the the only method science relies upon.
$\endgroup$ 8
