Induction on buffalo

First- and second- year undergrads often think that proof by induction* is extremely hard, even if they can actually do it without thinking. More than once I’ve had conversations with a student along these lines:
MJH- So what’s the problem?
Undergrad – I can see that this result is true but I don’t know how to prove it.
MJH – OK, why is true?
UG – Well it’s trivial if n=1, and [something simple] means that shows we have when n=2 and [the same simple thing] means we can get n=3 and keep repeating up to any number.
MJH – Exactly. That’s why it’s true.
UG – So how do I write that out?
MJH – Well it’s a basic induction. Write it out like all the examples of induction.
UG – INDUCTION!? I don’t know how to do proof by induction. It’s hard!
MJH- ARGH! You just did!!!one

So anyway, maths undergrads reading this, you can do induction. Well done. Good. Let’s do induction on strings of the word “buffalo”.

The single best title of any article on Wikipedia is Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo
. The notable thing about this string of “buffalo” is that it can be parsed as a sentence. This fact was first noted by the computational linguist William Rapaport of (naturally) the University of Buffalo. We use the facts that:
“buffalo” is a plural noun (1 buffalo, 2 buffalo,…);
“to buffalo” is a (somewhat rare) verb meaning “to bully”;
“Buffalo” is a city in the American state of New York and in English we may use city names as adjectives (e.g. “the London mayor is a laughing stock”).

This lets us parse the sentence as follows (this is taken form Wikipedia).

[Those] (Buffalo buffalo) [whom] (Buffalo buffalo buffalo) buffalo (Buffalo buffalo).

or

THE buffalo FROM Buffalo WHO ARE buffaloed BY buffalo FROM Buffalo ALSO buffalo THE buffalo FROM Buffalo.

. OK, but what does that have to do with proof by induction? Well we claim that, for each natural number n, we can repeat the word “buffalo” n times and then (give or take capitalisation) parse it as a sentence**.

The easiest way is to use induction to show that the odd cases (i.e. when there is k with n=2k+1) we can parse the sentence without needing the city meaning of “Buffalo”.

We have to treat n=1 as a special case, so lets take n=3 as our base case. We have the sentence,

Buffalo buffalo buffalo.

That is,

Bison bully bison.

Now we can add two “buffalo” by stating that the first buffalo themselves get buffaloed. That is

Buffalo buffalo buffalo buffalo buffalo.

read as

Buffalo [whom] buffalo buffalo [also] buffalo buffalo.

We can continue from there by pushing our first buffalo further still down the pecking order.

Buffalo [whom] (buffalo [whom] buffalo [also] buffalo) buffalo [also] buffalo buffalo.

Now we see what our induction ought to be. At each stage we have a sentence about a complex hierarchy of ungulate aggression,

Buffalo [whom] (buffalo [whom] (buffalo [whom](buffalo[whom].. … (buffalo [whom] buffalo [also] buffalo) … [also] buffalo)[also] buffalo)[also] buffalo)[also] buffalo buffalo.

We can obtain a sentence two “buffalo” longer, and of the same form, by adding that the buffalo at the top of current description are buffaloed in turn by still more dominant buffalo; that is by replacing the noun “buffalo” in the middle of the many nested brackets (the one with “[whom]” before it and “[also]” after it) with the noun phrase “buffalo [whom] buffalo [also] buffalo” By induction all odd length sequences of “buffalo” are sentences.

Finally we can add in a “Buffalo” (geographical adjective) to get the even length case. Note this isn’t actually how it is done in Rapaport’s original sentence where all buffalo are Buffalo buffalo.

It’s left as an exercise for the reader to write a maths post based on exploding whale

*Non-mathematicians should note the difference between mathematical induction and inductive reasoning. In maths speak induction is deductive.
**You may wish to argue as to whether that “Buffalo!” (an exclamation or order) is a sentence, in which case I say “meh” to your pettifogging pettifoggery.