1

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

Mac
  • 79
  • 1
    Yes, but only if you assume that the conditions hold for $n+1$ (rather than for $n$). – vadim123 Jan 10 '16 at 20:46
  • 1
    Or if say you want to prove for $n = 1,3,5,7...$ – fosho Jan 10 '16 at 20:48
  • 1
    Or for all even natural numbers – Peter Jan 10 '16 at 20:49
  • It would help if you gave a more complete description of what you are asking for. – paw88789 Jan 10 '16 at 21:15
  • It is common for induction to be split between even and odd cases. When this happens you can prove both base cases "n=1" and "n=2" then show that if it holds for k it holds for k+2 will suffice. Sometimes it is easier to go two up if the parity of n is important to the structure of the object in question. – Sean English Jan 10 '16 at 21:17
  • There even exist proofs by induction that step from $n$ to $n-1$… – Bernard Jan 10 '16 at 21:36

2 Answers2

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

vonbrand
  • 27,812
0

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

Raylan
  • 263