6
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ Mathematical induction is a way of checking a formula whether it works or not $\endgroup$
    – Ganesh
    Oct 29, 2016 at 11:06
  • $\begingroup$ @RAM Seems making it a biiiit clearer :) $\endgroup$
    – scarface
    Oct 29, 2016 at 11:07
  • $\begingroup$ I always like the analogy of an infinite line of dominos. How can you make sure they all fall over? First make the first domino fall over. Then make sure (when you set them out) than the $n^{th}$ domino will knock over the $n+1^{th}$ domino for any possible $n$. $\endgroup$
    – Ian Miller
    Oct 29, 2016 at 11:17
  • $\begingroup$ You may find this helpful: math.stackexchange.com/questions/19485/…, math.stackexchange.com/questions/869205/…. $\endgroup$ Oct 29, 2016 at 11:19
  • $\begingroup$ The reasoning modes are not that numerous, and had all been codified by Aristotle (-350). Not all exactly, and some of them had crept into mathematical prooving activity especially in number theory (infinite descend by Fermat for example,, some proofs by Euler as well), but the immense merit of Peano (1889 see (en.wikipedia.org/wiki/Peano_axioms)) has been to codify it as a proper prooving way as a part of his "axioms". The fact that it has appeared so late in Mathematics is a proof (!) that it wasn't evident... $\endgroup$
    – Jean Marie
    Oct 29, 2016 at 11:24

5 Answers 5

4
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Thank you, but what if I set a statement that is correct only in the basis step and is not correct for other positive integers? I assume that it works for $m$, so then it works for $(m+1)$. But in fact it works only in the basis step so for $m$ it can not be correct and therefore it can not be correct for $(m+1)$ as well. $\endgroup$
    – scarface
    Oct 29, 2016 at 11:27
  • $\begingroup$ If that is the case, then the induction won't work. $\endgroup$
    – Camille
    Oct 29, 2016 at 11:28
  • $\begingroup$ And how will the induction tell me that it will not work? How will I get that I can not prove it by induction? I just have to try to prove it with different proving method? $\endgroup$
    – scarface
    Oct 29, 2016 at 11:32
  • $\begingroup$ Let me explain a little bit. The inductive step doesn't assume anything on $m$, you have to prove $P(m+1)$ holds without having $m$ as a specific number. That is, you hold $P(m)$ to be true in terms of $m$, and try to show $P(m+1)$ is true. But if for some $k$ we have $P(k)$ is untrue, then there must exist a least $K$ such that $P(K)$ is untrue. Then when you try to perform the induction it will fail, because $P(K-1)$ is true does not imply $P(K)$ is true, so the attempt in the general $m$ case won't work also. $\endgroup$
    – Camille
    Oct 29, 2016 at 11:33
  • $\begingroup$ Good, thank you. Then I should google for some cases where mathematical induction fails and maybe it will be clear to me. $\endgroup$
    – scarface
    Oct 29, 2016 at 11:40
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.
$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .