What are the best examples of proof by mathematical induction on $n$ of statements of the form $\left( \forall n \in \{1,\ldots, N\}\,\,\Big(\cdots\cdots\cdots\Big) \right),$ where there's some good reason why there are only finitely many cases?
$\begingroup$ $\endgroup$
8 
- $\begingroup$ You can show by means of contradiction that an odd-length cycle cannot have a chromatic number of 2. Number the vertices from $v_1$ through $v_n$ such that $v_1$ is adjacent to $v_2$, $v_2$ is adjacent to $v_3$, etc, and $v_n$ is adjacent to $v_1$. Say we have two colors and without loss of generality, you color $v_1$ as red. You can show by induction that all the odd-labeled vertices must also be red. Since $n$ is odd and $v_n$ is adjacent to $v_1$, we then have two red vertices adjacent to each other, a contradiction. $\endgroup$benguin– benguin2017-04-01 00:08:34 +00:00Commented Apr 1, 2017 at 0:08
- $\begingroup$ Or if you don't want to deal with the nested proof by contradiction, you can prove using induction that if you want to color a path with two colors (say from $v_1 \to v_2 \to \dots \to v_n$) then all the odd numbered vertices must be the same color and all the even numbered vertices must be the same color (but different from the color used by the odd vertices) $\endgroup$benguin– benguin2017-04-01 00:22:37 +00:00Commented Apr 1, 2017 at 0:22
- $\begingroup$ I can think of several examples where (as with odd cycles) for any instance of the problem, you are doing induction on a finite set $\{1,2,\dots,n\}$, but there are instances of the problem with arbitrarily large $n$. Is this good enough, or are we looking for a problem with a global constant like $100$ such that we never need to run the inductive argument for more than $100$ steps? $\endgroup$Misha Lavrov– Misha Lavrov2017-04-01 03:37:55 +00:00Commented Apr 1, 2017 at 3:37
- $\begingroup$ @benguin : Correct me if I'm wrong, but it appears to me that the proposition about chromatic numbers of odd-length cycles is about ALL odd numbers, not about just finitely many odd numbers. Thus it is not an instance of what the question is about. $\endgroup$Michael Hardy– Michael Hardy2017-04-01 03:50:23 +00:00Commented Apr 1, 2017 at 3:50
- $\begingroup$ @Misha : Could you be specific about what sort of propositions you have in mind? $\endgroup$Michael Hardy– Michael Hardy2017-04-01 03:51:13 +00:00Commented Apr 1, 2017 at 3:51
| Show 3 more comments
1 Answer
$\begingroup$ $\endgroup$
1 There's the following unusual proof of (more or less) Fermat's little theorem: for all $x \in \mathbb F_p$, $x^p - x = 0$.
For $x=0$, we have $0^p - 0 = 0$. Assume that for some $x$, $x^p-x = 0$, and consider $(x+1)^p - (x+1)$. Because we're working in characteristic $p$, $(x+1)^p = x^p + 1$; therefore $$(x+1)^p - (x+1) = x^p + 1 - x - 1 = x^p - x = 0.$$ By induction, this claim holds for all $p$ values of $x$.
- 1$\begingroup$ The other proof I had in mind was the inductive part of proving the Lovász local lemma, which I think is not a legitimate enough example; it's an induction on all $k < n$, where $n$ is the (arbitrarily large) number of events being considered. $\endgroup$Misha Lavrov– Misha Lavrov2017-04-01 04:14:09 +00:00Commented Apr 1, 2017 at 4:14