Induction and contradiction

Question

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?

Answer 1

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

Answer 2

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.