How can I use "proof by contradiction" in an induction proof? I am wondering how I can show the second statement as a proof by contradiction:

Do I have something like
$(\begin{align}\forall n\geq n_{0}:A(n)\implies A(n+1)\end{align})\iff(\forall n\geq n_{0}:A(n)\land\neg A(n+1))$
or is it
$(\begin{align}\forall n\geq n_{0}:A(n)\implies A(n+1)\end{align})\iff(\exists n_{1}<n_{0}\in\mathbb{N}:A(n)\land\neg A(n+1))$?
I am not sure how to negate the statment. Many thanks in advance!
 A: I like to think of proof by induction as a proof by contradiction that the set of counterexamples of our statement must be empty.  Assume the set of counterexamples of $A(n): C= \{n \in \Bbb N \mid \lnot A(n) \}$ is non-empty.  Then $C$ is a non-empty set of non-negative integers, so it has to have a smallest element, $k$.
We prove directly that $A(0)$ is true so we know that $0$ can't be the least element of $C$; i.e., $k \neq 0$.  Therefore $k$ must have the form $m+1$ for some $m \in \Bbb N$.  Since $m \notin C$ (because by assumption $k=m+1$ is the least element of $C$ and $m \lt m+1$), we know that $A(m)$ holds.  But in our inductive step we've proved that $A(m) \Rightarrow A(m+1)$, so since we know $A(m)$ holds, the proof of the inductive step tells us that $A(m+1)$ also holds.  But that contradicts $m+1=k \in C$.
Therefore, our initial assumption that $C \neq \varnothing$ must be false and our set of counterexamples must be empty; in other words, $A(n)$ holds $\forall n \in \Bbb N$.
