What do we assume when we do proof by induction?

Question

I am having a little confusion when we do proof by induction. Lets start off with this, if I knew $(\forall x \in \mathbb{R} f(x) = 1)$, then I know that $(\forall y \in \mathbb{R} f(y) = 1)$ (and vice versa), so we can write $(\forall x \in \mathbb{R} f(x) = 1) \iff (\forall y \in \mathbb{R} f(y) = 1)$ because the substitution $x=y$ keeps my numbers in $\mathbb{R}$. Now my question is, when we write $n=k$ during our induction proof, are we assuming that $\forall k \in \mathbb{N}: P(k)$, or are we assuming $\exists k \in \mathbb{N}: P(k)$? I think that if we assume $\forall k \in \mathbb{N}: P(k)$ then it must immediately follow that $\forall k \in \mathbb{N}: P(k+1)$, so that doesnt seem right at all. (Asssuming $\exists k \in \mathbb{N}: P(k)$ doesn't mean that $P(k+1)$ must hold, as that is what we want to prove, that $\forall k \in \mathbb{N} P(k) \implies P(k+1))$. It's like I said, "Atleast one house on this street has a red door", if that was true, then I would not know if house $10$ has a red door or not, but if I said "all houses on this street have a red door", then it cannot be the case that house $10$ has any door but red. Does $(\exists k \in \mathbb{N}: P(k) \implies P(k+1))$ $\implies$ ($\forall k \in \mathbb{N}: P(k) \implies P(k+1))$ ??

Answer 1

The induction principle states the following: $\Big(P(0) \wedge (\forall k\in\Bbb N :P(k)\implies P(k+1))\Big) \implies \Big(\forall k\in\Bbb N : P(k)\Big)$

So to prove $\forall k\in\Bbb N : P(k)$ ones can instead prove two things:

• $P(0)$
• $\forall k\in\Bbb N :P(k)\implies P(k+1)$

Usually one proves $P(0)$ without much trouble.

To prove the second statement one begin by considering an arbitrary $k\in \Bbb N$ and then one needs to prove $P(k) \implies P(k+1)$.

To prove any statement of the form $S \implies T$, one assumes $S$ then proves $T$. In this case this means one assumes $P(k)$ then proves $P(k+1)$.

Then the implication $P(k) \implies P(k+1)$ is proved for an arbitrary $k\in \Bbb N$

That means $\forall k\in \Bbb N: P(k) \implies P(k+1)$ is proved.

Since the two statements are proved, the induction principle let us conclude that $\forall k\in \Bbb N: P(k)$.

Answer 2

Induction is is when you prove $P(0)$ is true, and prove that $P(n)\to P(n+1)$. Notice we never proved or assumed that $P(n)$ is true, we only showed that IF it is true, then it would follow that $P(n+1)$ is also true. The only statement that is proven true is $P(0)$.

UPDATE

In set theory, the only things that exist are sets. In general, sets exist based on axioms (assumptions we make that cannot be proven). For example, given any set and some property that describes some of its elements, then that too must also be a set (known as a subset or the subset axiom). Another example, we have to assume there exists at least one set (the existence axiom). With these two assumptions we can demonstrate that the empty set also exists. Some take the existence of the empty as an axiom instead (doesn't matter either way). There are other words we define for describing sets. For example, if set A exists, then we will define {A,{A}} (which also exists by the powerset axiom and subset axiom) to be called the successor. For convenience we will call the emptyset 0. Likewise whenever we have the set n we will define n+1 as the successor of n. We have just demonstrated how one constructs EACH natural number using basic principles of set theory.

However we now reach a pinnacle point in set theory. Does the set of all natural numbers exist? Each natural number itself exists, but does the collection exist? Unfortunately, not without another axiom. We must assume by axiom that there exists a set with two properties, called N. 1) that 0 is in N and 2) whenever n is in N, then n+1 is also in N. We cannot prove N exists, it must be assumed to exist (this is known as the axiom of infinity or the axiom of inductive sets).

Proof by induction then is nothing more than proving that some property about natural numbers creates a set that contains the natural numbers as a subset. For example, given the set A={n|n^2-1=(n+1)(n-1)} then induction is simply the process of showing that N is a subset of A. That is, by definition, show that 0 is in A, and then show that IF n is a number in A then n+1 must also be in A.

So induction is proving arbitrary sets contain the natural numbers. The FACT that the natural numbers are defined inductively is an assumption that cannot be proven and must just be accepted as an axiom of mathematics. The reason induction is the way it is, is because we defined it that way.

Answer 3

Now my question is, when we write $n=k$ during our induction proof, are we assuming that $\forall k \in \mathbb{N}: P(k)$, or are we assuming $\exists k \in \mathbb{N}: P(k)$?

We are not assuming either of those.

As pointed out in jjagmath's answer, one of the steps in an induction proof is to prove the statement "$\forall k\in\Bbb N :P(k)\implies P(k+1)$." In order to prove that statement, we assume the following two things, and nothing else:

• $k \in \Bbb N$
• $P(k)$

Assuming these things is similar to, but not quite the same as, assuming $\exists k \in \mathbb{N}: P(k)$.

If we were to assume $\exists k \in \mathbb{N}: P(k)$, that would merely mean "the predicate $P$ is true for at least one number." On the other hand, when we assume $k \in \Bbb N$ and $P(k)$, we are not merely assuming that the predicate $P$ is true for at least one number; we are also assuming that the name "$k$" refers to one of the numbers for which $P$ is true.

You may be thinking, "Isn't it true that for all $k \in \Bbb N$, we're assuming $P(k)$?" The answer is... kind of. I admit that it's true that if you think about "what's really happening" in the proof, then you find out that for every possible value of $k$, we assume, at one time or another, that $P(k)$ holds. On the other hand, the statement $\forall k \in \mathbb{N}: P(k)$ means something else—that statement would basically mean that we're making all of those assumptions at the same time. But we're not doing that; we're only making the assumption for one number at a time.

Answer 4

Maybe the metaphor of the falling dominoes helps.

You've set up a long row of dominoes, and you want to find out what would happen if you toppled the first domino.

You look at the first two dominoes to check their distance, their weight, etc. You come to the conclusion that "if domino 1 falls, then domino 2 will fall".

You check the next two and again conclude "if domino 2 falls, then domino 3 falls". (If you combine this with the first step, you can now conclude that "if domino 1 falls, then dominoes 2 and 3 fall".)

Similarly, you check that "if domino 3 falls, then domino 4 falls". (If you combine this with the first two steps, you can conclude that "if domino 1 falls, then dominoes 2, 3 and 4 fall".)

And so on, until you reach the end of the line.

When you combine all these steps, you can conclude that the if you topple the first one, all dominoes will fall.

And the interesting thing is: You could prove that without toppling any dominoes! No dominoes have fallen yet. In other words: If we use $D$ for the set of dominoes and $f(d)$ for the statement that domino $d$ has fallen, then neither $\forall d \in D \colon f(d)$ nor $\exists d \in D \colon f(d)$ is true yet.

But having to check each pair of dominoes is pretty tedious, isn't it? If numbers were like dominoes, we'd have to do something like this:

• Prove that if $P(0)$ is true, then $P(1)$ is true.
• Prove that if $P(1)$ is true, then $P(2)$ is true.
• Prove that if $P(2)$ is true, then $P(3)$ is true.
• ...

Fortunately, in math we don't deal with physical entities which may have different distances, weights, etc. Numbers are exactly defined, so we can replace all these steps by one general idea:

• Prove that if $P(n)$ is true, then $P(n + 1)$ is true.

This one proof replaces the (infinitely) long list of proofs above. All we need to know for this is that $n$ is a natural number. We don't care which one.

We also don't have to know whether $P$ is actually true for any $n$. We don't assume $\exists n \colon P(n)$.

We can even prove something silly, for example "if $n$ is irrational, then $n+1$ is irrational". That's a logically correct implication!

_{(Of course, if we tried to complete the proof by induction that all natural numbers are irrational, we'd find that there's no base case. Zero isn't irrational, and neither is any other natural number we could try to use as a starting point. Metaphorically speaking: There's no initial domino we could topple.)}

In a nutshell: To get an intuitive grasp of proof by induction, I think it makes sense to think of the induction step as a template for infinitely many concrete steps.

And if we can also prove that our property holds for a specific base case, then we have proven that it also holds for all following cases, which makes the proof by induction complete.

Hope that helps...

Answer 5

Say there's a bunch of students in a math class. So far, none of them understand proof by induction.

But if one person in the class understood induction, she'd think it's great, and she'd explain it to another student, and as soon as the other student understands it, he'll tell yet another student about it, and so on, until everyone in the class understands it.

See what I did there?

I proved by induction that if one person in the class understands induction, then soon all will understand it.

But the key word here is if.

I didn't assume that anyone understands it yet. All I'm saying is that if someone understands it, she'll explain it to the next person. It's hypothetical. I'm not saying that it has happened, or is going to happen. Just that if it happens, then something else will happen as well.

I hope that helps answer your question what we assume when we do proof by induction.

I'd say we don't assume much at all. In a way, we assume $P(n)$, but that's just a hypothesis. We're not saying there actually is an $n$ for which $P$ is true. We're not saying $\exists n \colon P(n)$. Just that if $P(n)$ is true for some hypothetical $n$, then $P(n+1)$ is also true.

If we can prove this if-then implication for our particular $P$, then we're mostly done with our proof by induction. All that's left to do is find a base case (usually zero or one) and show that $P$ is true for that case.

In the math class metaphor, the base case is the first student who understands induction. If we can explain it to one student, she'll tell the next student, and so on, and then each student will learn it sooner or later.

(Unfortunately, there doesn't seem to be a nice symbol – like "$\exists$" or "$\forall$" – for this kind of hypothesis. Maybe that adds to the confusion – that the language of formal logic as it is usually taught doesn't have a symbol for such hypotheses.)