How do I pick a basis case in proof by induction when the start of the range is unclear?

Question

Proof by induction requires a basis case which is a starting value in a sequence such as n=0. Assume we're proving a theorem which doesn't have a clear basis case. It can be any value from -infinity to +infinity. Which value is chosen for the basis case? Moreover, how do we pick a value for a basis case when there's discontinuity in the range of values, i.e. there are subsequences of invalid values for n in the range?

Answer 1

The trick is to prove the inductive step with whatever large-$n$ assumptions you need, find out where we can start such an inductive step, then check when the first sufficiently large base case occurs.

Suppose, for example, we want to prove all sufficiently large positive integers $n$ satisfy $2^n>n^2$, and we want to work out what "sufficiently large" means. Since$$2^k>k^2\implies 2^{k+1}>2k^2\ge k^2+3k\ge k^2+2k+1$$(where the first $\ge$ uses $k\ge3$ and the second uses $k\ge 1$), any valid case $n\ge3$ is the starting point of induction. You can verify it'll be $n=5$.

Answer 2

It generally doesn't matter. The main idea is often that $P(n)$ is true for all sufficiently large integers $n$.

Presumably, there is some integer beyond which there are no more interruptions (if that's not the case, i.e., if there are arbitrarily large $n$ for which $P(n)$ doesn't hold, then you're trying to prove a theorem that is false).

So you must take as your base case an integer beyond the interruptions. If needed, you can then manually demonstrate the (finite number of) cases before that between the interruptions. The theorem you will have proved by induction is "For all $n\geq N_{\textrm{base}}$, the statement $P(n)$ is true." Proving $P(n)$ for smaller $n$ is icing on the cake.