Induction through Failure

I was inspired by a recent post from Ben Blum-Smith about induction to talk about an approach to induction I learned from Al Cuoco.  I don’t know its origins, but it really does a nice job of dealing with the issue Ben brings up: you assume you’re right then prove it.  But if you’re already right, why prove it?

Our curriculum (CME Project Precalculus Investigation 4A, for those playing at home) ties induction to the process of finding closed-form rules to match recursive definitions, such as this one:

f(n) = f(n-1) + 5, f(0) = 3

What is f(23)?  All the formula says is that f(23) = f(22) + 5, so that’s no good… except that it is, since now you do the same thing to f(22), eventually working your way back to the “base case”.  This actually works out pretty nicely:

f(23) = f(22) + 5

= [f(21) + 5] + 5

= f(20) + 5 + 5 + 5

\vdots

= f(0) + 5 + 5 + \cdots + 5

But how many fives?  Why is chasing it all the way back to f(0) a good idea?  What would change with f(117)? with f(n)?  This works to find closed-form rules for recursions surprisingly often.

Another way to find f(23) is to count off outputs: f(1), f(2), \dots until you reach 23.  More likely, you’ll figure out a pattern to the outputs before you get there… 3, 8, 13, 18…

So now you’ve got these two rules:

f(n) = f(n-1) + 5, f(0) = 3 \qquad \text{and} \qquad g(n) = 5n + 3

If I want to prove these two rules will always agree (whenever f is defined, anyway) it’s time for induction.  Before that, we really want to be sure the rules agree.  This is where technology comes in: using Excel or the TI-Nspire or several other tools, these functions can be entered then compared.  (For the Nspire, see page 3 of this document for an example.)  Now use the technology to compare f(23) and g(23) … f(500) and g(500) … f(100000) and g(100000).

No matter what piece of technology you use, at some point it is going to stop saying that these two functions agree.  (On Nspire hardware, this happens somewhere around 100, but depends on the device’s memory.)  Say for example that the technology agrees that f(105) = g(105) but f(106) is undefined.  How could you show that f(106) = g(106) anyway?

By doing this, the “induction step” process is one that actually happens with a numeric value.  So let’s work this one out… evaluating f(106) fails, but we know from its definition that

f(106) = f(105) + 5

Oh and we also know that f(105) = g(105), because the functions agreed up to that point.  So:

f(106) = g(105) + 5

= (5 \cdot 105 + 3) + 5

= 5 \cdot 106 + 3

= g(106)

The induction step happens naturally, based on the failure of the technology, and based on a numeric example.  (Now, try to show that f(107) = g(107)…)

The steps taken above also evolve quickly into a general argument for f(n) simply by using n instead of 106, and noting that 105 should be (n-1).

f(n) = f(n-1) + 5

= g(n-1) + 5

= (5(n-1) + 3) + 5

= 5n + 3

= g(n)

And, boom goes the dynamite.

I feel this method does a nice job of dealing with the “proving what you know to be true” issue that surrounds induction.  This method can also help with some of the issues around base cases, because it encourages the checking of several cases before trying to complete an inductive proof.  Lastly, the extension from the numeric calculation of f(106) to the algebraic calculation of f(n) lines up well with one of Common Core’s mathematical practices, “Look for and express regularity in repeated reasoning“.  After all, that’s what induction is all about…

About these ads

About Bowen Kerins
Bowen is one of the lead authors of CME Project, a high school mathematics curriculum focused on mathematical habits of mind. Bowen leads professional development nationally, primarily on how math content can be taught with a focus on higher-level goals. Bowen is also a champion pinball player and once won $1,000 for knowing the number of degrees in a right angle.

2 Responses to Induction through Failure

  1. That’s pretty rad. I love the way that the failure of technology is motivating the induction step.

    Have you gotten a chance to field test this yet? Did that turn up anything interesting? Right now I’m imagining some students having trouble getting it up to do the manipulation to prove the 106 case, on the grounds that “look, it’s definitely going to agree for the next one, because it just agreed A HUNDRED AND FIVE TIMES!” Did you see any of that?

    • Bowen Kerins says:

      This was originally part of a curriculum called “Mathematical Methods in High School”, field tested then published in 1999; an article in Mathematics Teacher about this method can be found online at

      http://www.nctm.org/eresources/article_summary.asp?URI=MT2001-09-489a

      We get around the issue you describe by peppering different choices for the variable instead of trying every case. So the kids compare f(1) and g(1), maybe f(2) and g(2), but then we use the technology to check out f(10) and g(10) … f(20) and g(20) … f(100) and g(100) … f(1000) and g(1000). Hopefully somewhere in there the technology runs out of memory on the recursion. It begs the question of when the recursion “stops working” and the challenge of whether it really did stop working.

      This is one reason Excel and other spreadsheet programs are less suited for this task, since their recursive results can be seen one step at a time, and you really would see all 105 successes (actually, way more than that) before the recursion fails. I wonder if there is a way to directly create the recursive definition in Excel (and not by cell formula).

      I have used the TI-Nspire for this, as well as the 83/84 and 89. The Nspire is especially suited to creating recursive definitions, since the notation onscreen can look identical to the way it looks in the book.

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.

Join 30 other followers

%d bloggers like this: