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.

About these ads

5 Responses to “Induction on buffalo”

  1. Phil H Says:

    The style of this entry reminds me of the proof (by induction) of the proposition that ‘Alexander the Great did not exist, and he had an infinite number of limbs’: http://www.fortfreedom.org/b19.htm.

  2. vanity 800 Says:

    Howdy, I found this site by accident when I was going through Google then I went to your website. I have to say your website is very interesting I just love the theme! donít have much free-time at the current moment to fully read through your website web sitebut I have bookmarked it. I will be back in a day or two. Thanks for a great site.

  3. Shasta Feazelle Says:

    You created a superb position with what you mentioned. People have to read your posting so they can obtain a far better viewpoint on this concern. It was great of you to offer great facts and supporting arguments. After reading this, I know my mind is extremely certain about the matter. Continue the fantastic work!

  4. customer satifaction survey Says:

    When I initially commented I clicked the “Notify me when new comments are added” checkbox and
    now each time a comment is added I get three e-mails
    with the same comment. Is there any way you can remove me from
    that service? Appreciate it!

  5. mass effect trilogy game Says:

    The child may balk at this, but there are options available.

    http://www.play station 3.com are perfectly safe for you to explore and interact with, it runs smooth on the
    fusion bolt beat the living daylight on some expensive well known
    brands is heart warming. Building artificial walls into the world of child entertainment
    and become a subject of many studies and researches
    for its presumed role in influencing child behavior and psychology.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: