# 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}?

I am not sure how to negate the statment. Many thanks in advance!

• When you talk about "the second statement", what do you refer to? Commented Jan 13, 2022 at 22:52
• @Taroccoesbrocco I meant part ii),i.e. the inductive step.
– Hans
Commented Jan 13, 2022 at 22:58
• So, where does $n_0$ come from in your attempts? It does not appear in the statement (ii). Commented Jan 13, 2022 at 23:34
• Yes, my bad. $n_{0}$ could be equal to 1. I think I had the slightly more genereal version in mind. It is the base case.
– Hans
Commented Jan 13, 2022 at 23:36

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

• Thanks for the answer! Isn't that sort of the argument for showing that the induction principle is equivalent to the Well-Ordering-Principle? However, I don't quite see how this answers my question, since it was more about how correctly negate the the statement/quantifiers, I think.
– Hans
Commented Jan 13, 2022 at 23:16
• Yes, it's an equivalence I often find useful. I'm not sure what statement you're trying to negate. I thought you were asking how to reframe a proof by induction as a proof by contradiction. Commented Jan 13, 2022 at 23:23
• Okay I see. What I would like to know is, if I can show part ii) by contradiction, i.e. show that $A(n)\land\neg A(n+1)$ is false. What somehow puzzles me is wheather I have $\exists n_{1}< n_{0}$, which I think comes from negating the entire statement or if I have $\forall n\geq n_{o}:A(n)\land\neg A(n+1)$.
– Hans
Commented Jan 13, 2022 at 23:33
• @Hans Translate "whenever" in statement (ii) to mean $\forall$. To prove the second statement by contradiction, assume that $\exists k ~(k \in S \land k+1 \notin S)$ and then derive a contradiction from that assumption. Commented Jan 13, 2022 at 23:40