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.

So I see that the process for proof by induction is the following (using the following statement for sake of example: $P(n)$ is the formula for the sum of natural numbers $\leq n$: $0 + 1 + \cdots +n = (n(n+1))/2$ )

  1. Show that the base case is trivially true: $P(0)$: let $n = 0$. Then $0 = (0(0+1))/2$, which is true.
  2. Show that if $P(k)$ holds then $P(k+1)$ also holds. Assume $P(k)$ holds for some unspecified value of $k$. It must be then shown that $P(k+1)$ holds.

This is the part I don't get: 'Assume $P(k)$ holds'

We are just assuming something is true and then 'proving' that something else is true based on that assumption. But we never proved the assumption itself is true so it doesnt seem to hold up to me. Oviously proof by induction works so am I viewing the process incorrectly?

share|improve this question
3  
You prove the base case $P(0)$. You prove that $P(n) \Rightarrow P(n+1)$. Ergo, from $P(0)$, we may conclude $P(1)$, and hence $P(2)$, etc. –  Zhen Lin Feb 6 '12 at 19:14
1  
See also this previous answer. –  Arturo Magidin Feb 6 '12 at 19:30
    
I can't remember an example, but I have seen a situation where the base case was hard, and the induction step easy. –  André Nicolas Feb 6 '12 at 20:30
    
Also be wary of 'proof by invalid induction', where the proof of inductive step only works for k > 0 –  wim Feb 7 '12 at 1:30
    

8 Answers 8

up vote 10 down vote accepted

The "inductive step" is a proof of an implication: $$\mathbf{if}\ P(k),\ \mathbf{then}\ P(k+1).$$ So we are trying to prove an implication.

When proving an implication, instead of proving the implication, we usually assume the antecedent (the clause after "if" and before "then"), and then use that to prove the consequent (the clause after "then"). There are several reasons why this is reasonable, and one reason why it is valid.

Reasonable:

  1. An implication, $P\to Q$, is false only in the case where $P$ is true but $Q$ is false. In any other combination of "truth values", the implication is true. So in order to show that $P\to Q$ is valid (always true), it is enough to consider the case when $P$ is already true: if $P$ is false, then the implication will be true regardless of what $Q$ is.

  2. More informally: in proving $P\to Q$, we can say: "if $P$ is false, then it doesn't matter what happens to $Q$, and we are done; if $P$ is true, then..." and proceed from there.

Why is it a valid method of proof?

There is something called the Deduction Theorem. What it says is that if, from the assumption that $P$ is true, you can produce a valid proof that shows that $Q$ is true, then there is a recipe that will take that proof and transform it into a valid proof that $P\to Q$ is true. And, conversely, if you can produce a valid proof that $P\to Q$ is true, then from the assumption that $P$ is true you can produce a proof that shows that $Q$ is true.

The real interesting part of the Deduction Theorem is the first part, though: that if you can produce a proof of $Q$ from the assumption that $P$ is true, then you can produce a proof of $P\to Q$ without assuming anything about $P$ (or about $Q$). It justifies the informal argument given above.

That's why, in mathematics, whenever we are trying to prove an implication, we always assume the antecedent is already true: the Deduction Theorem tells us that this is a valid method of proving the implication.

share|improve this answer

You have to prove a logical implication in the process of using induction.

We can express this implication as $P \to Q$, where $P,Q$ are statements.

To prove that $ P \to Q$ is true, we consider whether $P$ is true or false. If $P $ is false, then the entire implication is true. Ex falso quodlibet.

So we assume that $P$ is true and deduce that $Q$ is also true. This is the standard way to prove a logical implication directly.

share|improve this answer
    
Note that the "P" that I use corresponds (fortunately or not...) to your "P(k)" –  The Chaz 2.0 Feb 6 '12 at 19:20

You are almost correct. But observe:

You proved it was true for $n=1$; thus, using 2. you know it's true for $n=2$.

Well, it's true for $n=2$. So, using 2., it's true for $n=3$.

$\ \ \ \vdots$

share|improve this answer
    
The question is about why we don't prove the assumption. –  The Chaz 2.0 Feb 6 '12 at 19:20
    
The OP actually proved it was true for $n=0$. –  Quinn Culver Feb 6 '12 at 22:23

It is like a self proving prophecy. This is the standard process. Assume for a sec there was a flaw in the process and you were assuming P(n) was true but expected the property as (0(0+1))/3 instead of (0(0+1))/2. You would not be able to solve for the n + 1 case. Try it.

share|improve this answer

Maybe the following helps:

A statement $P(n)$ about natural numbers $n$ can be very complicated, much more complicated than the formula for the sum $1+2+3+\ldots+n$. Given an arbitrary such statement it will be true for some $n$ and false for other $n$. At any rate it is reasonable to consider the set ${\cal P}$ of $n$s for which it is true: $${\cal P}\ :=\ \{n\in{\mathbb N}\ |\ P(n)\ {\rm true}\}\ .$$

Now you can talk about the induction axiom for subsets $A\subset{\mathbb N}$. Such subsets have a "static quality" and seem to be much more innocuous objects than "statements $P(n)$ about natural numbers $n$". The axiom reads as follows:

Induction axiom for sets: Let $A$ be a subset of ${\mathbb N_{\geq0}}$. If $0\in A$ and for all $n$ from $n\in A$ follows $n+1\in A$, then $A={\mathbb N}$.

This sounds pretty believable. It just says that by just counting away from $0$ no number is left out.

share|improve this answer

The point is you see what happens if $P(k)$ is true. If you show that $P(k) \implies P(k+1)$ is true, then because you've shown it works for 0 it will work for all the other natural numbers.

share|improve this answer

The key lies in that the assumption P(n) either comes as true or false exclusively. If P(n) comes as true, and we show that P(n+1) follows, then by the deduction theorem (P(n)->P(n+1)) holds true. If P(n) comes as false, then (P(n)->P(n+1)) by definition of the material conditional. Of the 16 possible truth functions, only the material conditional expresses the implication in mind here.

You might want to note that (as somewhat hinted at by others here) not all induction proofs require assuming P(n) to prove the implication (P(n)->P(n+1)). For instance, with your formula 0+1+⋯+n=(n(n+1))/2, if you look at (P(n+1)-P(n)) on the left hand side of the "=" sign, and (P(n+1)-P(n)) on the right hand side you can figure out that they equal each other. So, the rate of change between P(n) and P(n+1) comes as the same for both sides. Thus, the implication (P(n)->P(n+1)) follows.

share|improve this answer

Here is a very prosaic way to think about it. Imagine a pond has lily pads lined up forever in a straight line. Also, imagine you have a frog, who is guaranteed to hop on the next lily pad if he hops on any lily pad.

What is true if you place the frog on the first pad? Well, he will hop on the second. Since he hops on the second, he will visit the third. This process will keep going on. You can see that the frog will eventually visit all of the pads.

This is how the principle of induction works.

So there are two basic steps to an induction argument. Show it works for some first value. This it the base case. (Place Mr. Frog on the first pad)

Now show that the truth of the argument for a positive integer $n$ guarantees it is true for $n + 1$; this is the induction step. Then it is true for all positive integers beyond the first one you showed it was true for in the base case.

share|improve this answer

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.