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?
[Math] Induction and contradiction
induction
Related Solutions
The inductive step is a proof of an implication: you are proving that if the property you want holds for $k$, then it holds for $k+1$.
It is a result of formal logic that if you can prove $P\rightarrow Q$ (that $P$ implies $Q$), then from $P$ you can prove $Q$; and conversely, that if from assuming that $P$ is true you can prove $Q$, then you can in fact prove $P\rightarrow Q$.
We do this pretty much every time we prove something. For example, suppose you want to prove that if $n$ is a natural number, then $n^2$ is a natural number. How do we start? "Let $n$ be a natural number." Wait! Why are you allowed to just assume that you already have a natural number? Shouldn't you have to start by proving it's a natural number? The answer is no, we don't have to, because we are not trying to prove an absolute, we are trying to prove a conditional statement: that if $n$ is a natural number, then something happens. So we may begin by assuming we are already in the case where the antecedent is true. (Intuitively, this is because if the antecedent is false, then the implication is necessarily true and there is nothing to be done; formally, it is because the Deduction Theorem, which is what I described above, tells you that if you manage to find a formal proof that ends with "$n^2$ is a natural number" by assuming that "$n$ is a natural number" is true, then you can use that proof to produce a formal proof that establishes the implication "if $n$ is a natural number then $n^2$ is a natural number"; we don't have to go through the exercise of actually producing the latter proof, we know it's "out there").
We do that in Calculus: "if $\lim\limits_{x\to x_0}f(x) = a$ and $\lim\limits_{x\to x_0}g(x) = b$, then $\lim\limits_{x\to x_0}(f(x)+g(x)) = a+b$." How do we prove this? We begin by assuming that the limit of $f(x)$ as $x\to x_0$ is $a$, and that the limit of $g(x)$ as $x\to x_0$ is $b$. We assume the premise/antecedent, and proceed to try to prove the consequent.
What this means in the case of induction is that, since the "Inductive Step" is actually a statement that says that an implication holds: $$\mbox{"It" holds for $k$}\rightarrow \mbox{"it" holds for $k+1$},$$ then in order to prove this implication we can begin by assuming that the antecedent is already true, and then proceed to prove the consequent. Assuming that the antecedent is true is precisely the "Induction Hypothesis".
When you are done with the inductive step, you have in fact not proven that it holds for any particular number, you have only shown that if it holds for a particular number $k$, then it must hold for the next number $k+1$. It is a conditional statement, not an absolute one.
It is only when you combine that conditional statement with the base, which is an absolute statement that says "it" holds for a specific number, that you can conclude that the original statement holds for all natural numbers (greater than or equal to the base).
Since you mention dominoes in your title, I assume you are familiar with the standard metaphor of induction like dominoes that are standing all in a row falling. The inductive step is like arguing that all the dominoes will fall if you topple the first one (without actually toppling it): first, you argue that each domino is sufficiently close to the next domino so that if one falls, then the next one falls. You are not tumbling every domino. And when you argue this, you argue along the lines of "suppose this one falls; since it's length is ...", that is, you assume it falls in order to argue the next one will then fall. This is the same with the inductive step.
In a sense you are right that it feels like "cheating" to assume what you want; but the point is that you aren't really assuming what you want. Again, the inductive step does not in fact establish that the result holds for any number, it only establishes a conditional statement. If the result happens to hold for some $k$, then it would necessarily have to also hold for $k+1$. But we are completely silent on whether it actually holds for $k$ or not. We are not saying anything about that at the inductive-step stage.
Added: Here's an example to emphasize that the "inductive step" does not make any absolute statement, but only a conditional statement: Suppose you want to prove that for all natural numbers $n$, $n+1 = n$.
Inductive step. Induction Hypothesis: The statement holds for $k$; that is, I'm assuming that $k+1 = k$.
To be proven: The statement holds for $k+1$. Indeed: notice that since $k+1= k$, then adding one to both sides of the equation we have $(k+1)+1 = k+1$; this proves the statement holds for $k+1$. QED
This is a perfectly valid proof! It says that if $k+1=k$, then $(k+1)+1=k+1$. This is true! Of course, the antecedent is never true, but the implication is. The reason this is not a full proof by induction of a false statement is that there is no "base"; the inductive step only proves the conditional, nothing more.
By the way: Yes, most proofs by induction that one encounters early on involve algebraic manipulations, but not all proofs by induction are of that kind. Consider the following simplified game of Nim: there are a certain number of matchsticks, and players alternate taking $1$, $2$, or $3$ matchsticks every turn. The person who takes the last matchstick wins.
Proposition. In the simplified game above, the first player has a winning strategy if the number of matchsticks is not divisible by $4$, and the second player has a winning strategy if the number of matchsticks is divisible by 4.
The proof is by (strong) induction, and it involves no algebraic manipulations whatsoever.
The argument is off a bit: in fact, $[\forall k \in \mathbb{N}, k < 0 \rightarrow P(k)]$ is vacuously true. This is because for any $k \in \mathbb{N}$, $k < 0$ is false, so the implication $k < 0 \rightarrow P(k)$ is true. So, if you've proven the required statement $\forall n \in \mathbb{N}, [ \forall k \in \mathbb{N}, k < n \rightarrow P(k) ] \rightarrow P(n)$, then the special case with $n=0$ always has the hypothesis true, which implies that the conclusion $P(0)$ is also true.
As for your bogus proof that all natural numbers are even: in applying the inductive hypothesis, you're implicitly assuming that $n-2 \in \mathbb{N}$. But for $n=0$ and for $n=1$, this is not valid, so it is not valid to apply the inductive hypothesis. And in fact, $[\forall k \in \mathbb{N}, k < 1 \rightarrow P(k)] \rightarrow P(1)$ is false: the hypothesis is true because the only possible $k$ is $k=0$, but the conclusion $P(1)$ is invalid.
(For a similar situation in which an inductive proof looks good at first, but on closer examination the proof of the inductive step implicitly assumes $n$ is large and the argument breaks down for small $n$: see the bogus proof that "all horses are the same color".)
This illustrates what will often happen in practical proofs by strong induction: there will in fact be cases in which you cannot apply the inductive hypothesis to smaller cases, so you will have to prove those cases by a separate argument. These special cases will end up looking very much like base cases.
So, for instance, the following argument that every natural number is either even or odd is valid: we assume the strong inductive hypothesis $[\forall k \in \mathbb{N}, k < n \rightarrow even(k) \vee odd(k)]$; and we need to prove $even(n) \vee odd(n)$. Now if $n=0$, $n$ is even; and if $n=1$, $n$ is odd. Otherwise, $n-2 \in \mathbb{N}$ and $n-2 < n$, so by the inductive hypothesis, either $n-2$ is even or $n-2$ is odd. In the first case, $n = (n-2) + 2$ is even; in the second case, $n = (n-2) + 2$ is odd.
Best Answer
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)$$