Induction with $n+2$

Question

When proving something via induction, is one allowed to do the induction step, showing that the conditions work for $n+2$, instead of $n+1$?

Answer 1

That depends on what your conditions are. If youre trying to inductively reason by using increments of 2, then no. The principle of induction relies on the fact that if you prove it for a base case, and then for every successive number of a number for which your statement has already been proven, youve proven it for all numbers following (and including) the base case. If you would prove it using the way Ive interpreted your solution you would only prove your statement for a base case $n$, and then for $n+2k, k \in \mathbb{N}$.

Answer 2

As the comments say, you'd need base cases $n = 0$ and $n = 1$ to be able to conclude the claim holds for all $\mathbb{N}$.

For example, say you want to prove that the Fibonacci numbers defined as $F_0 = 0$, $F_1 = 1$ and $F_{n + 2} = F_{n + 1} + F_n$ if $n \ge 0$ are such that $F_n \le \tau^{n - 1}$, where $\tau \approx 1.618$ is the positive zero of $z^2 = z + 1$ (the golden section; yes, this is quite loose, but still).

Bases: $F_0 \le \tau^{-1}$ and $F_1 \le \tau^0$ are both true.

Induction: Assume it is true for $n$ and $n + 1$, consider $n + 2$:

$\begin{align} F_{n + 2} &= F_{n + 1} + F_{n} \\ &\le \tau^n + \tau^{n - 1} \\ &= \tau^{n - 1} (\tau + 1) \\ &= \tau^{n - 1} \cdot \tau^2 \\ &= \tau^{n + 1} \end{align}$

This is the claim for $n + 2$.

Conclusion: Together with the bases, we can conclude that the claim is true for all $n \ge 0$.