Question about proving with Mathematical Induction (some confusions on the concept)

Question

While proving a statement of $f(n)$ using mathematical induction we do the following-

• we prove it for some natural number which satisfies the condition of $n$.
• We assume it true for some $k$.
• Then we try to prove it for $k+1$ by using the statement obtained by assuming it to be true for $k$.

Now,my question is that we see that the proof using $k+1$ is totally dependent on proof using $k$.But there is no guarantee that the statement is true for k.We have only assumed it.Our assumption maybe right or wrong.The how can be prove $k+1$ on the basis of k if it is not certain that k is true. Please help.Thank You.

Answer 1

Indeed what you described in the second part is not complete. As it stands, it is a proof of a conditional : if $P(k)$ is true, then so is $P(k+1)$. What you're missing is that you have also a base case. You showed there is an $n$ such that $P(n)$ holds, and thus your proposition is true for all $k\ge n$.

Answer 2

Let's say you have proved that if $f(k)$ is true, then $f(k + 1)$ is true. In your base case, you have also proved that $f(n)$ is true for some $n$. Now, with both these in mind, we can conclude that $f(n + 1), f(n + 2), f(n + 3), \dots$ are all true.

In other words, the assumption that $f(k)$ is true may be right or wrong for arbitrary $k$, but there exists at least one $k$ for which it is true, namely $k = n$ which was shown in the base case.

Answer 3

Let' clarify the concept on a specific example.

We know that $$1+2+\cdots +n=\frac{n(n+1)}2.\tag 1$$

Prove this statement a fake naive way:

1. Observe that $(1)$ is true for $n=2$. Indeed, $$3=1+2=\frac {2\times 3}2.\tag 2$$
2. Observe that you can prove the same for $n=3$ based on $(2)$ now: $$6=1+2+3=\frac{2\times3}2+3=\frac{2\times3+2\times3}2=\frac{3\times 4}{2}.\tag 3$$
3. You do it once again for $1+2+3+4$ based on $(3)$: $$1+2+3+4=(1+2+3)+4=$$$$=\frac{3\times 4}2+4=\frac{3\times4+2\times 4}2=\frac{4\times5}2.$$
4. You notice the pattern now and try to do it in general:

$$1+2+\cdots n+n+1=\frac{n(n+1)}2+n+1=$$ $$=\frac{n(n+1)+2(n+1)}2=\frac{(n+1)(n+2)}2.$$ You generalize the idea now: If I could do it for $2$ and if I could do it for $n+1$ knowing that it is true for $n$ then it will be true for any natural number.

One more step ahead and you say that if this principle worked for the property $$1+2+\cdots +n=\frac{n(n+1)}{2}$$ then it will work for any property $P(n)$.

We've seen that every proof based on the principle of mathematical induction could be done step by step for any $n$. In that case you do not assume that the statement is true for an $n$ but you directly prove that. So, mathematical induction is a practical simplification of a special kind of inductive proof as long as we talk about the truth of a statement for finitely many $n$'s. The principle of mathematical induction becomes an unproven axiom if it comes to the statement that something is true for all $n$.