Here's a little illustration if you need to show that a few examples do not make a proof.

(Context: Introducing a quick 4 days on proof by induction, because we use it in the next unit on Series & Sequences.)

First I asked them to write an expression for the nth term of the sum of the first n positive odd integers. Like this:

1 = 1

1 + 3 = 4

1 + 3 + 5 = 9

1 + 3 + 5 + 7 = 16

They did up to like n = 5, saw the pattern, and settled on n squared. They were utterly convinced. Their intuition was serving them well. For now.

Then, I drew a circle on the Smartboard, and asked them, if we draw n unique points on the circle, and connect them with as many segments as possible, in how many maximum regions is the circle divided?

2 points: 2 regions

3 points: 4 regions

(At this point, they had a few minutes to work independently or with a partner to come up with a conjecture for number of regions in terms of n points on the circle.)

4 points: 8 regions

They think they see it: the number of regions doubles. They check it with

5 points: 16 regions

And nearly everyone was satisfied with that, and conjectured that n points yield regions.

A few intrepid souls, and eventually all with some cajoling, drew 6 points, yielding 31 regions, not the expected 32.

Coming up with the actual expression is non-trivial (it ends up involving nCr, of all things), and we didn't get into it, but I found this an effective motivator for introducing proof by induction.

Last year, I used the example of Fermat's conjecture that $2^{2^n}+1$ yields only primes - a conjecture which went unproven either way until Leonhard Euler found a factorization of $2^{2^5}+1=4292967297=(641)(6700417)$. But, I thought this was much more effective, because they could confront their erroneous conjecture with the counterexample directly.

Kate, I love this problem! I wrote up my experiences with it recently. Want me to send that to you? (I showed it to some folks at the institute last summer, and again at one of my math salons.)

ReplyDeleteI love these pattern problems. Do you read 360's blog? There are some great posts there that fit this theme. Here's what I found with a cursory search:

ReplyDeletehttp://threesixty360.wordpress.com/2008/07/24/4-6-8-10-12-14what-comes-next/

http://threesixty360.wordpress.com/2009/01/25/whats-the-pattern/

And this most recent post which has one of my new favorite ever induction problems (maybe too advanced for 8th graders? since it involves nCr and such as well):

http://threesixty360.wordpress.com/2009/04/20/pascals-pyramid-part-1-of-3/

A similar effect happens when you take a sphere and cut it up into patches using n planes through the center. The first one divides the sphere into two hemispheres. The second one divides each of those into two pieces. The third one divides each of

ReplyDeletethoseinto two pieces, and the fourth...It's actually a really great problem to work on.

Sue - I think you should post it on your blog. :-)

ReplyDeleteDave I read 360 but really just started recently. I'll check out the links - thanks!

unapologetic - is that the same result as dividing a closed 2D region with n lines? (.5n^2+.5n+1 - I think that's right) 3D is hard to visualize.

That's a great example. Thanks for sharing it.

ReplyDeleteI recently wrote about a similar case of a pattern breaking down as you increase the number of dimensions of a particular construction. In this case an intuitive property of spheres and cubes holds until you reach 10 dimensions.

Kate: It might. You could show it is by finding the formula and seeing if they're the same.

ReplyDeleteOr you could go for elegance points and construct explicit bijections! That is, for each n give a method to translate from the diagrams you're talking about to the configurations I'm talking about. This not only shows that the number of regions must be the same, but it gives an explicit recipe for showing

howthey're the same.11PM on Tuesday, April 21, 2009: my blog assigned me homework.

ReplyDeleteI'm going to DO IT, too, as soon as I go read up on just what exactly a bijection is again.

I mean, you know, aside from the fact that you just explained it.

ReplyDeleteWell, I could post it on my blog. But it's the solution, and I didn't really want to wreck the problem by posting the solution.

ReplyDeleteSue - Good point! Thanks for offering, but I've already figured out a solution. I just didn't know it off the top of my head when I was typing up the post.

ReplyDelete