Question about proving with Mathematical Induction (some confusions on the concept) 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. 
 A: 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.
A: 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$.
A: 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:


*

*Observe that $(1)$ is true for $n=2$. Indeed, $$3=1+2=\frac {2\times 3}2.\tag 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$$

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

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