3
$\begingroup$

There are always two kinds of induction in general:

  • Assume that the result holds for $n-1$
  • Assume the the result holds for integers $<n$

For the former one, we only need to check one base case; for the latter one, we always need to check two base cases.

I’m learning group theory. Induction is a very useful tool that is always employed. We always prove by induction on group order $|G|$ and assume that results hold for groups of order $<|G|$. But I find that we always check only one base, namely $|G|=1$! Maybe I misunderstood something, but I really don’t remember seeing any proof checking more than one base case.

So what is the point? Could you give me some ideas? Any help would be appreciated!

Possible examples:

$\endgroup$
  • $\begingroup$ Which proofs do you have in mind? $\endgroup$ – lhf Aug 9 at 15:15
  • 7
    $\begingroup$ There's some confusion in :"for ... strong induction, we always need to check two base cases." In general, strong induction involves no base case. Of course, in particular cases, you might have a proof that works for large $n$ but not for 1 or 2 (or 17) small values of $n$, and then you have to check those values separately, and you might call them base cases, but that's a peculiarity of the particular proof, not of the method of strong induction. $\endgroup$ – Andreas Blass Aug 9 at 15:17
  • $\begingroup$ @Ihf math.stackexchange.com/questions/560924/… $\endgroup$ – Benjamin Aug 9 at 15:18
  • 2
    $\begingroup$ Show that $S\subset \mathbb N$, $1\in S$ and if $k\in S$ for $k<n$, then $n\in S$ implies that $S=\mathbb N$. You can prove it by "weak" induction if you like. Two base cases are not needed. $\endgroup$ – Justin Young Aug 9 at 15:24
  • $\begingroup$ You don't need to check groups of smaller order because all statements are true for groups of order at most $0$. $\endgroup$ – David A. Craven Aug 9 at 15:45
2
$\begingroup$

Here are some reasons why one might want to check more than one base case:

  • the argument used in the inductive step cannot be applied for small $n$, hence the proof writer checks those cases separately in the base cases
  • the inductive step (proof for $n+1$) explicitly refers to the cases $n$ and $n-1$ (sometimes also $n-2$ etc.)
  • the writer might want to get a better feeling for what needs to be shown, and therefore checks the statement manually for more $n$ than actually needed.

In general, it is therefore a good idea to start (on a separate sheet of paper) with the inductive step. Afterwards, you know which base cases need to be checked.

The same applies for reading a proof: If you wonder why more than one base case was treated, take a look at the inductive step. The answer will most likely be hidden there.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ All sheep are pink. To prove this, we start by showing that all sheep are the same color. As a base case, one sheep is one color. For induction, suppose that any group of $k$ sheep are the same color, and consider a group of $k+1$ sheep. Remove one of the sheep---the remainder are the same color, by induction. Remove a second sheep, and replace the first one. This group is also mono-colored. Therefore the entire collection of $k+1$ sheep has only one color. By induction, all sheep are the same color. Regarding the statement of the result: $\endgroup$ – Xander Henderson Aug 9 at 15:41
  • 1
  • 1
    $\begingroup$ (This is an example of your second point; the induction here actually requires a second base case, in which there are two sheep). $\endgroup$ – Xander Henderson Aug 9 at 15:42
  • 2
    $\begingroup$ One could also say that this is an example of the first point, since the inductive argument cannot be applied when dealing with two sheep. $\endgroup$ – Zuy Aug 9 at 15:50
  • $\begingroup$ Indeed. Still, one of my favorite examples. $\endgroup$ – Xander Henderson Aug 9 at 16:07
1
$\begingroup$

Here is an induction that requires more than one base case. Say we have two stamps, one 5 cent and the other 3 cents. I claim that any number $n \geq 8$ can be made using just these two stamps. First we have $5+3=8$ and we have $3 + 3+ 3=9$. From these two base cases we can construct the next number by either replacing a $5$ with two $3$s or replace three $3$s with two $5$s. to complete the induction. Note that we do need the two base cases to ensure there will always be enough $5$s or $3$s to make the replacement for the inductive step.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.