I recently read about the false inductive proof that all horses are the same colour. There are some mathSE threads about this already (MathSE_thread_1, MathSE_thread_2).
After reading this, I now realise I have never really understood mathematical induction. It seems obvious for sums, but when presented with this example I was stumped.
I have some questions:
Question 1. The inductive step
for all horses are the same colour goes roughly as follows:
Assume that there are n horses, numbered 1 to n. By induction horses 1 through (n-1) are the same colour, and similarly horses 2 through n are the same colour. The overlapping sets H_0 = {1,2,...,(n-1)} and H_1 = {2,3,...,n} imply that horse 1 and horse n are the same colour. Thus all horses are the same colour.
I have an issue with one of the statements:
By induction horses 1 through (n-1) are the same colour, and similarly horses 2 through n are the same colour.
I understand why horses 1 through (n-1) are the same colour (by hypothesis), but why can we just say horse n is the same colour? It seems to imply the numbering is arbitrary to me, but then induction is completely invalid unless we can define an order?
Question 2. The base case:
If we grant the inductive step reasoning (of which I am unsure whether that is valid), the induction relies on the fact that for some k, two distinct k-1 subsets have shared elements, from which we can conclude they are all the same colour. So the base case should be n=2 (or should it be n=3?).
However the trick used in the inductive step seems to imply the numbering of the horses is arbritary (as I briefly mentioned above), so a subset of size n=2 would seem to require we prove all subsets of size 2 have horses which are the same colour, which makes the induction step redundant?
General Question 3.
How do we choose what inductive steps are valid, and what base cases are required? I realise this is poorly phrased, but is there a way in general, or a set of heuristics to enable a valid basis to be chosen?
A slightly modified version of Mathematical Induction that seems to me more intuitive
Perhaps my understanding of induction is incorrect. It seems to me mathematical induction is more intuitive when presented as follows:
For each positive integer n > n_0, Let p(n) be a statement.
Step 1. We first show that If p(k) then p(k+1) is true for every positive integer k. To do this we choose an arbitrary k and show, by direct proof usually, this implies (k+1)
Step 2. Choose a base case n_0 on which we induct on to all n > n_0. Here we use the fact that we have shown that for an arbritrary k, k+1 is implied. Choosing a valid basis allows the "induction domino effect" to work its magic.
Then we have shown p(n) is true for every positive integer n > n_0
That seems to me easier to understand. Although do we need to explicitly show our base case implies n_0 + 1?
I suppose this is a different way of asking the same question I asked above, namely how do we choose valid base cases?
Hopefully this question isn't too rambling. Please let me know if anything requires clarification.