How can mathematical induction prove something?

Question

I am learning mathematical induction, and the concept still does not fit in my mind. I just cannot understand how I can prove something just by:

1) basis: calculating whether it fits for the minimal $n$, where $n$ belongs to $N$.

2) inductive step: I JUST assume that the statement that I set at the start works for any $n\leq m$, then it also works for $(m+1)$

On what basis can I say that the statement is proven? Based on the fact that I have found the formula from the first part of the inductive step in the formula of the second part of the inductive step, substituting the first one for the second and getting the same result as I assumed in the inductive step?

I cannot get it. Maybe I am misunderstanding the whole concept of mathematical induction. If that is the truth, then I am sorry.

Can anyone explain to me in human language why I can say that a statement is proven when I perform mathematical induction on that statement?

Answer 1

I'll explain weak induction, which is probably what you're learning. Let's say you want to prove a statement for $n\geq N$. Say this statement is $P(n)$.

1) Basis step: Prove the statement for $n=N$, i.e. $P(N)$ is true.

2) Inductive step: Suppose $P(m)$ is true for some $m\geq N$. Then you use this assumption to prove that $P(m+1)$ is true.

How the two steps work is as follows. In the inductive step you should have proved $P(m+1)$ is true using $P(m)$ is true, without explicitly stating what $m$ is (in other words, you DON'T substitute it with a number, say 100 or something).

This means that no matter what $m$ is, it will always be the case that when $P(m)$ is true, then $P(m+1)$ is true, and this holds for all $m\geq N$.

Now in the basis step, you have proved $P(N)$ is true. By the preceding paragraph, this means $P(N+1)$ is true. Then $P(N+2)$ is true. Then $P(N+3)$ is true, and so on. So $P(n)$ is true for all $n\geq N$.

Answer 2

This might give you an alternative (and clarifying) look on induction.

If $A$ denotes a non-empty subset of $\mathbb N$ then some $k\in\mathbb N$ exists such that: $$m\in\mathbb N\wedge m<k\implies m\notin A$$

In words: every non-empty subset of $\mathbb N$ has a smallest element $k$.

Proving by induction that $P(n)$ is true for every $n\in\mathbb N$ is actually the same thing as proving that the set $A:=\{n\in\mathbb N\mid \neg P(n)\}$ has no smallest element, hence must be empty.

You start by assuming that $k\in A$ and serves as its smallest element. Then the basic step tells you that $k\neq1$. That means that $k$ is a successor: $k=m+1$. Then $m<k$ so $m\notin A$. That means exactly that $P(m)$ is a true statement However, the induction step now tells us that also $P(m+1)$ is a true statement, i.e. that $k=m+1\notin A$. So a contradiction is found.

Answer 3

The technique sets up an infinite chain of implications:

The base case $m = n$ proofs your statement $S$ for the start of the chain, $S(n)$ is true then.

The inductive step $m \to m + 1$ is performed for arbitrary $m$ where just $m \ge n$ must be met. This gives all those implications \begin{align} S(n) & \Rightarrow S(n + 1) \\ S(n+1) & \Rightarrow S((n + 1) + 1) = S(n + 2) \\ S(n+2) & \Rightarrow S((n + 2) + 1) = S(n + 3) \\ \end{align} and so on. So for any $m$ (with $m \ge n$) there is a chain of implications starting at $n$, reaching $m$ in finite many steps. Thus $S(n) \Rightarrow S(m)$.

Based on what I can say that the statement is proven?

You prove the base case, here $n$. And then you need to proof that if you assume the statement $S$ for the case $m$ ($m \ge n$) to be true, let us call this instance $S(m)$ then also the case $m+1$ would be true, thus $S(m) \Rightarrow S(m+1)$.

Finally the principle of induction grants you the truth of the statement $S$ for all $m \ge n$.

Answer 4

I prefer to think of the proof technique in terms of counting. The usual definition of the set of natural numbers (following Peano's axioms) is that

• $0$ is a natural number
• Whenever $n$ is a natural number, then $n+1$ is also a natural number
• Nothing else is a natural number

In other words: The natural numbers are the numbers that you can construct by counting upwards from $0$.

So to prove that a property $P(n)$ holds for every natural number, then you must prove that

• $P(0)$ holds. That is, that the property holds for the first natural number
• If $P(n)$ holds, then $P(n+1)$ will also hold. That is, the property will continue to hold, when you count upwards.

Answer 5

So suppose that you have some theorem, and you have followed the two steps (check the base case, and did the inductive step). Now I doubt whether the theorem is actually true for $n = 6$. How can you convince me?

Well, note that you have shown that if the theorem is true for $n = 5$, then it is true for $n = 6$. So if I accept your proof of the inductive step, then all you need to do is convince me that the theorem is true for $n = 5$, right?

But wait, if you can convince me that it is true for $n = 4$, then again by the inductive step, I would have to admit that it is true for $n = 5$, and hence for $n = 6$ as well.

Actually, by continuing this reasoning for a few more steps, we have to conclude that you only have to convince me that the theorem is true for $n = 1$. Then, by the induction hypothesis, it is true for $n = 2$, which you an take as the assumption of the induction hypothesis once more, so it is true for $n = 3$, etc.

Of course, the induction step starts with "if it is true for ...". So you cannot continue applying it "backwards" forever: at some point you have to work out one of the cases explicitly to show that the assumption is met without invoking the induction hypothesis. This is the base case, and we choose it to be as simple as possible -- usually, $n = 0$ or $n = 1$.

However, once you have this, you can apply the induction hypothesis forward an infinite number of times: as soon as you have done step 2 enough times to show that the theorem is valid for $n = 9{,}173{,}212{,}907{,}542$ just apply it once more and it is also valid for $n = 9{,}173{,}212{,}907{,}543$, etc.