A Question About The First Step In Induction

Question

I am currently learning mathematical induction from this site (https://www.mathsisfun.com/algebra/mathematical-induction.html). It has broken induction into 3 steps:

1. Show that it is true for n=1
2. Assume it is true for n=k
3. Show that it is true for n=k+1

I have 4 questions:

1. Why, of all numbers do we pick n=1? Can't we pick something like n=1, n=2, or the like?

2. Why do we need the 3rd step? I get a feeling it is to prove that it is true for all n=k, but if that is so, how does it do it? It does prove that it is true for all n=k+1, but that is based on the assumption that n=k; and therefore doesn't prove it. Because if a proof is based on an assumption, how does that prove anything?

3. Why do we need the first step when we show that it is true for all n=k+1?

4. In n=k+1, why do we add 1? Why can't we subtract 1, or add 2, etc? Why must it be n=k+1?

Is it possible to answer the question at the level of a Pre-Calc student, who hasn't learnt Calculus (obviously), set theory, and all those complicated stuff?

This question is different from "Dominoes and induction, or how does induction work?" because I have learnt neither limit notation nor L'Hopital's rule, and the other question contains them. This is important for a Precalc student who understands neither of them.

Answer 1

1. You can prove it for $n=2$ or even $n=1000$ but then the induction proves the statement is true for $N\geq 1000$ rather than $N\geq 1$. It really depends on what you are trying to prove.

The rest of the questions sound a little like rambling because you do not understand what is happening when you use a proof by induction. I will try to explain that to you.

So first we prove that the statement is true for $n=1$ (or some other number, that is irrelevant).

Next, we show that if the statement is true for $n=k$ then it is true for $n=k+1$. Keep in mind, that we have not proved that the statement is true for $n=k$, we have proved the implication, " If the statement is true for $n=k$, then it is true for $n=k+1$". In layman terms, we have proved that if the statement is true for some number, then the statement has to be true for the next one.

Once we have done that, we go back to the first step we have done. We have shown that the statement is true for $n=1$, by our proof, that means the statement is true for the next number, $n=2$. But now, we know it is true for the next number $n=3$. etc, we do that continuously and so we have proven that the statement is true for all $N\geq 1$

Regarding question 4. If you prove the implication for $n=k+2$ then try to think why the reasoning above does not apply.

Answer 2

Close your eyes and imagine you have a three years old boy and a very tall ladder.

The boy learns how to climb one step at the time.

If the boy does not get on the ladder then you can relax.

On the other hand if the boy somehow gets on the first step of the ladder you will soon find him on the second and on the third and so forth.

Thus it is important to start at some point and it could be one or two or any other integer.It is also important to know that we can go one step higher at any time. Now if you have P(1) and if you can conclude P(k+1) from P(k), and if you accept the Mathematical Induction as a valid proof, then the statement P(n) is true for all $n\ge 1 $

Answer 3

Actually steps 2 and 3 should be grouped: what we have to prove is that from one case follows the next case, i.e. if we denote the property to be proved as $P(k)$, we really prove this: $$\forall k,\enspace P(k)\implies P(k+1),$$ and as for all implications, to prove $\;A\implies B$, we show that if the premise $A$ is true, then the conclusion $B$ is necessarily true.

Intuitively, why does this work?

Well we've proved the initial case $n=1$ (or whatever …). If the inductive step has been proved, there follows that the case $n=2$ is true. So the case $n=3$ is true. Repeat this, say, 99 times, and you've proved it's true for $n=100$.

The induction theorem asserts that if you've proved an initial case $n_0$, and you've proved the inductive step: $P(n)\implies P(n+1)$ (not $P(n)$ nor $P(n+1)$ alone, but the implication), then $P(n)$ is true for all $n\ge n_0$.