0

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?

Hanul Jeon
  • 27,376
user148298
  • 121

2 Answers2

0

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

J.G.
  • 115,835
0

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.

MPW
  • 43,638
  • So a proof by induction is valid so long as you carefully spell out your assumptions about n. So thereotically I can prove n(n+1)/n and show it is true for n=0 and n=1 and then add the caveat "for all whole number values where n is between 0 and 1 inclusive" and call it a day? Cool! I could have ruled Discrete Math! – user148298 Nov 22 '19 at 16:27
  • @user148298 : Not quite following what you mean. You could show directly that it is true for $n=3$ (a base step) and show that if it is true for $n$ then it is true for $n+1$ (the inductive step); in that case, you will have shown that it is true for all integers $n \geq 3$. You will not be making any statement about 0, 1, or 2. If you don't do the inductive step, then you will only have shown it is true for whatever small number of base cases you directly showed. A "proof by induction" always involves the inductive step, which proves truth for some tail of uninterrupted integers. – MPW Nov 22 '19 at 16:40
  • @user148298 : The point is that proving that something is true for (say) all integers $\geq 126$ doesn't mean it is false for smaller integers, it just means you haven't proven it for those smaller integers yet. – MPW Nov 22 '19 at 16:42