# Induction and contradiction

I want to prove a statement by induction , I tasted the base case, then I considered the induction hypothesis for $n$ , so I assumed by absurdity that is not true for $n + 1$ but this contradicts the induction hypothesis , this proof is correct ? This idea is right ? If I suppose that is not valid for $n + 1$ and this contradicts the induction hypothesis , then this is proof?

• If you are doing everything you say right, then this valid to me. – Jendrik Stelzner Jan 6 '16 at 12:44
• This looks like a technique very similar to induction (essentially the same). Assume the statement does not hold for all $n$. Consider the smallest $n$ such that the statement does not hold and note $n > 1$ (or $n > 0$) because of the base case. Prove it does also not hold for $n-1$, contradicting the minimality of $n$. – user158189 Jan 6 '16 at 13:17

## 2 Answers

Given a property $P$ and a base case, $n_0$, the following implication is verified (this is simple induction law): $$\left[P(n_0) \land \forall n \geq n_0\color{blue}{\Big(P(n) \implies P(n + 1)\Big)}\right] \implies \forall n \geq n_0 \Big(P(n)\Big)$$

If we change the blue part by another equivalent expression, then the main implication will still being correct (so you will be able to argue as described by the result expression).

Consider logical variables $p$ and $q$ defined as: $$p = P(n) \text{ is verified}$$ $$q = P(n + 1) \text{ is verified}$$

So, by logical equivalences:

\begin{align}p \to q &\equiv \lnot p \lor q\\ &\equiv\lnot p \lor q \lor \text{false}\\ &\equiv\lnot (\lnot(\lnot p \lor q)) \lor \text{false}\\ &\equiv\lnot ( p \land \lnot q) \lor \text{false}\\ &\equiv(p \land \lnot q) \to \text{false} \end{align}

That is exactly what you refere to: considere as a hypothesis [$P(n)$ true and $P(n+1)$ false] and get a contradiction.

So, your method works: $$\left[P(n_0) \land \forall n \geq n_0\color{blue}{\Big(P(n) \land \lnot P(n+1)\implies \text{false}\Big)}\right] \implies \forall n \geq n_0 \Big(P(n)\Big)$$

• Nice typography~ – DanielV Jan 6 '16 at 18:45
• Thanks! I tried to write the most formal justification as I could (as OP method was obviously correct, in terms of logic). – JnxF Jan 6 '16 at 20:26

Induction and contradiction goes something like this - We test some base case. Assume that the proposition is not true for all nonnegative integers. Then there exists some integers for which the proposition fails. If the set of integers for which the proposition fails is nonempty then it must have a least integer,call it $m$. Since base cases exist we have $m-1$ as true. And then we derive that the truth of $(m-1)^{th}$ case implies the truth of $m^{th}$ case. A contradiction. Thus we conclude that the set that we assumed to be nonempty must be empty. And that completes the proof by induction.

• I've been researching and found out that the reasoning is bandstand , what I did was prove the contrapositive (by contraposition search on google) – Israel Meireles Chrisostomo Jan 16 '16 at 0:59