Induction and Implication The axiom of induction in logical symbols is: 
$$
\forall P[[P(0) \land \forall k \in N (P(k) \implies P(k+1))] \implies \forall n \in N[P(n)]]
$$
If $P(0)$ is true and $P(k)$ is false (therefore $P(k) \implies P(k+1)$ is true), does it mean $P(n)$ is true?
I understand induction, but not implication.
 A: It may help to read $P(k)\Rightarrow P(k+1)$ as "it is not possible for $P(k)$ to be true while $P(k+1)$ is false".
In itself it is possible for $P(k)\Rightarrow P(k+1)$ to hold if $P(k)$ is false -- but in the specific context of induction this will not happen, because the truth of $P(k)$ is already guaranteed by $P(0)$ and the earlier instances of the induction step.
Note that $P(k)\Rightarrow P(k+1)$ has to be proved for every possible $k$, not just for a particular one.

One way to think of induction is to consider an indirect proof. Suppose that $P(0)$ and that $P(k)\Rightarrow P(k+1)$ for all $k$. Now assume for a contradiction that $P(n)$ is not true for all $n$. Then there must be a smallest $n$ such that $P(n)$ fails.
This smallest $n$ cannot be $0$, because we're explicitly assuming $P(0)$. So $n-1\ge 0$. Consider the particular instance of $P(k)\Rightarrow P(k+1)$ that has $k=n-1$. This says $P(n-1)\Rightarrow P(n)$, or in other words it is not possible for $P(n-1)$ to be true while $P(n)$ is false. But that is exactly the situation we're in here, because $n$ was the first $n$ such that $P(n)$ is false, so $P(n-1)$ is true. This is a contradiction, so our assumption that $P(n)$ is false for some $n$ must be rejected.
