# Mathematical induction question: why can we “assume $P(k)$ holds”?

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?

• 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
• 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
• en.wikipedia.org/wiki/Mathematical_induction#Axiom_of_induction – user2468 Mar 12 '12 at 1:00

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.

• I know this is very old but you explain things very well so I thought to ask you this : I understand that we can assume P is true until we prove Q is true and then once we find out Q is true we can say that P is true. But why do we ignore the case where Q is true yet P is false? Since the latter case still holds true? – K.M. Dec 28 '17 at 13:20
• @K.M.: No, you don't understand, because your statement is incorrect. We assume P is true, and from that deduce Q is true. We do not then assert that P is true. That is not the case. What we can then do is say that the implication $P\to Q$ holds. The entire implication, not P itself. We are trying to prove that the implication holds. When the antecedent, P, is false, the implication is true regardless of Q; when the consequent Q is true, the implication is true regardless. So we don't need to worry about those cases, as in that case the implication holds. – Arturo Magidin Dec 29 '17 at 14:05

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.

• 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$

• 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.

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.

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.

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.

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.