Is there a general rule for how to pick the base case value for proofs by mathematical induction?

Question

I was looking at how to do mathematical induction. One source said to use $n = 1$ for the basis step. But I have seen other sources choose the value $n = 0$.

So the question is as follows:

Question: How do I know when it is right to use $n = 0$ versus $n = 1$? I don't see a pattern. Is there a general rule about how to pick the value?

This source uses $n = 1$: http://www.mathsisfun.com/algebra/mathematical-induction.html

This source uses $n = 1$: http://cims.nyu.edu/~kiryl/teaching/aa/review1.pdf

But this source uses $n = 0$: http://www.cs.odu.edu/~toida/nerzic/level-a/induction/example1/example1.html

But how can't $n = 1$ be used for the problem in the last source? I'm confused.

Answer 1

Is there a general rule about how to pick the value?

This answer largely address that question.

---

Comment: First a note about the links you provided: the second link actually has an example (Example 4) that starts with $n=0$ as a base case (not every example has $n=1$ as a base case), and the last link involves what JMoravitz addressed in a comment, namely the difference in how some people consider $\mathbb{N}$ (that is, whether or not $\mathbb{N}$ includes $0$).

---

That being said, there are a few things worth addressing to answer your question in a general sense:

1. The base case for a proof that uses mathematical induction may start at any integer whatever.
2. Sometimes you need more than one base case to get a proof started effectively.
3. Occasionally the choice for the appropriate base case is more of an "art" than anything else.
4. There are instances where you have to "discover" what value you should use for a base case.

I'll address each of these points separately.

---

(1): Most often (and no doubt the motivation for your question) you will come across problems that require you to start at $n=0$ or $n=1$ for your induction proof. Regardless, context is what always matters most in induction proofs, for your base case may start at any integer, as pointed out by David Gunderson in his book Handbook of Mathematical Induction:

The base case for mathematical induction need not be $1$ (or $0$); in fact, one may start at any integer. (p. 36)

Weirdly enough, if you need to, you can also construct an induction argument that uses a negative integer as a base case. To see more about this, I'd encourage you to read my answer here that goes into more detail about starting with a negative integer as a base case.

As mentioned, context is really the important thing when constructing proofs by induction. Many claims are not for $n=0$ or $n=1$ but something else entirely. For example:

• For $n\geq 3$, we have $(n!)^2>n^n$.
• For $n\geq 4$, we have $2^n<n!$.
• For $n\geq 5$, we have $(2n)!<(n!)^24^{n-1}$.
• For $n\geq 6$, we have $6n+6<2^n$.
• For $n\geq 10$, we have $3n^2+3n+1<2^n$.
• And so on ad infinitum.

(2): When proving results involving Fibonacci numbers, a form of strong induction is occasionally useful. In particular, the inductive step in many proofs is of the form $[P(k-1)\land S(k)]\to S(k+1)]$. In such instance two base cases are often required. For example:

If $n>5$, then $F_n>\left(\frac{3}{2}\right)^{n-1}$.

To prove the above result, you would first want to verify it for $n=6$ and $n=7$. (You would then make reference to these bases cases in your proof.)

(3): Suppose you encounter the following problem:

For $n\geq 1$, show that $15\mid\bigl(4(47)^{4n}+3(17)^{4n}-7\bigr)$.

Your first inclination would probably be simply to plug in $n=1$, but this results in having to check that $19769280$ is divisible by $15$, and it is ($19769280=15\cdot 1317952$), but that is rather annoying to verify. It would be much easier to check that $0$ is divisible by $15$, something that requires no effort at all to verify. The point is that you could have noticed that the claim is also true for $n=0$ with the base case being easier to verify. Hence, proving the statement for all $n\geq 0$ is actually easier.

(4): In some instances (admittedly not often), you actually have to discover or figure out the value of $c$ for which your statement is true for all $n\geq c$. For example, suppose you encounter the following problem (Exercise 176 from David Gunderson's book):

Prove by induction that for $n$ sufficiently large, $n!>4^n$.

After testing out a sample of $n$-values, it appears that the statement is true for all $n\geq 9$. Of course, you have to construct a proof by induction now with what you feel like is an appropriate base case (i.e., $n=9$). This actually checks out, and it is rather easy to verify. If the statement were not true until some $n$-value later on down the line, then you would not be able to construct a valid induction proof. Hence, sometimes you actually have to tinker around a bit to see what the "best" base case to start with is.

---

There are probably more points to mention about base cases, but those are the more salient ones as I see it.