# Base case when applying induction in group theory

There are always two kinds of induction in general:

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

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:

• Which proofs do you have in mind? – lhf Aug 9 at 15:15
• 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. – Andreas Blass Aug 9 at 15:17
• – Benjamin Aug 9 at 15:18
• 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. – Justin Young Aug 9 at 15:24
• You don't need to check groups of smaller order because all statements are true for groups of order at most $0$. – David A. Craven Aug 9 at 15:45

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.

• 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: – Xander Henderson Aug 9 at 15:41
• (This is an example of your second point; the induction here actually requires a second base case, in which there are two sheep). – Xander Henderson Aug 9 at 15:42
• 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. – Zuy Aug 9 at 15:50
• Indeed. Still, one of my favorite examples. – Xander Henderson Aug 9 at 16:07

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.