Why can we assume a statement is true for $n = k$, when using induction?

Question

I know the principle of mathematical induction. The only thing that causes my confusion is that we suppose a statement is true for $n=k$ then we prove the statement is also true for $n=k+1$ but how can we suppose $n=k$ to be true? What if a statement is true for $n=k+1$ and is not true for $n=k$? Does $k$ mean to be starting from $1$ or $2$ if in the base case we prove the statement to be valid for $n=1$? Please help me with this confusion.

Answer 1

Suppose we show, for a range of values of $k$, that $S(k)\implies S(k+1)$ for any $ k$ in the range.. This does not imply that $S(k)$ is true for any $k$. For example,when $S(k)$ is $k=k+1$ then we can prove that $S(k)\implies S(k+1).$

If you can exhibit some $k_0\in N$ such that $S(k_0)$ is true, and if you can show that $S(k)\implies S(k+1)$ for any natural number $k\geq k_0,$ then you have proved $\forall k\in N\;(k\geq k_0\implies S(k).$

Explanation : We can show that if $\exists k\geq k_0\; (\;\neg S(k)\;)$ then we have a paradox: There would be a least such $k$, which we can call $k_1$ . Now $k_1>k_0$ because we know $S(k_0)$ is true. Then $k_1-1\geq k_0,$ and $S(k_1-1)$ is true, otherwise $k_1$ would not be the LEAST $k\geq k_0$ such that $\neg S(k).$ But then we have $S(k_1-1)$ and also $S(k_1-1)\implies S(k_1)$ , so we have $S(k_1),$ contradicting $\neg S(k_1)$.

Answer 2

Imagine the theorem you are trying to prove is a set of stairs and proving the theorem amounts to getting to the top of the stairs in this analogy. Proving the base case amounts to climbing the first step. Think of the inductive step as follows: if you manage to get yourself to the $n^{th}$ step, then you can get to the $(n +1)^{th}$ step. So if you can get to the $1^{st}$ step (base case), you can get to the next step, i.e. the $2^{nd}$ step. But then you can get to the $3^{rd}$, and then to the $4^{th}$, and so on until you eventually reach the top of the stairs and yell "Huzzah!" because you have proved your theorem.