In one-step induction, why sometimes there are 2 base cases?

Question

I noticed in various induction proofs, that it uses 2 base cases (e. g: for $n = 1$ and $2$ the problem trivially holds...)

Why is that? Isn't one base case enough for one-step induction?

Answer 1

While it's true that one base case is sufficient, it is sometimes more convenient to prove more base cases first.

To be more explicit:

1. Suppose you only prove $P(n)$ for $n = 1$. In this case, you have to prove that $$P(n) \implies P(n+1) \quad \forall n \ge 1.$$

2. Suppose you prove $P(n)$ for $n = 1, 2$. In this case, you have to prove that $$P(n) \implies P(n+1) \quad \forall n \ge 2.$$

Depending on $P(n)$, the latter might be easier to do.

---

To be more illustrative, consider the following stupid example:
Let $P(n)$ be the proposition $``\ a_n \le 1000"$, where $a_n$ is defined as: $$a_1 = 10, a_2 = 100,$$ $$a_{n+1} = a_{n} \quad \forall n \ge 2.$$

Hopefully, you can see why it's better to take two base cases.

Answer 2

For example.

Prove that: $$\frac{1}{n+1}+\frac{1}{n+3}+\frac{1}{n+5}+...+\frac{1}{3n-1}\geq\frac{1}{2}$$ for any natural $n$.

For the proof by induction we need to check $n=1$ and $n=2$ because we need a transition from $n$ to $n+2$.

I'll write a full proof and I hope it would be clear.

For $n=1$ we need to check: $$\frac{1}{2}\geq\frac{1}{2},$$ which is true.

For $n=2$ we need to check: $$\frac{1}{3}+\frac{1}{5}\geq\frac{1}{2}$$ or $$\frac{8}{15}\geq\frac{1}{2},$$ which is true.

Now, it's enough to prove that: $$\frac{1}{n+1}+\frac{1}{n+3}+\frac{1}{n+5}+...+\frac{1}{3n-1}\geq\frac{1}{2}\Rightarrow$$ $$\Rightarrow\frac{1}{n+3}+\frac{1}{n+5}+...+\frac{1}{3n-1}+\frac{1}{3n+1}+\frac{1}{3n+3}+\frac{1}{3n+5}\geq\frac{1}{2},$$ for which it's enough to proof that: $$\frac{1}{2}-\frac{1}{n+1}+\frac{1}{3n+1}+\frac{1}{3n+3}+\frac{1}{3n+5}\geq\frac{1}{2}$$ or $$\frac{1}{3n+1}+\frac{1}{3n+5}\geq\frac{2}{3(n+1)},$$ which is true by C-S: $$\frac{1}{3n+1}+\frac{1}{3n+5}\geq\frac{(1+1)^2}{3n+1+3n+5}=\frac{2}{3(n+1)}$$ and by induction we are done!

Answer 3

Use two base cases when the next case depends on the two previous cases. For example,

the Fibonacci numbers could be defined by $ F_n=F_{n-1}+F_{n-2}$ with $F_1=F_2=1$,

and it can be shown by induction that $F_n=\dfrac{(1+\sqrt5)^n-(1-\sqrt5)^n}{2^n\sqrt5}$,

but we need two cases to start off the induction,

because the $n^{th}$ Fibonacci number is defined in terms of the two previous Fibonacci numbers.