Posted by: Dave Richeson | October 22, 2009

Thoughts on teaching induction

I don’t plan on doing this very often, but I thought I’d re-post one of my earlier blog posts—one that I wrote a year ago, when I had many fewer readers. Now is an appropriate time for me to re-post it because I am currently teaching induction in my Discrete Mathematics course. Enjoy.

In their article “Some observations on teaching induction,” (MAA Focus, May/June 2008, pp. 9–10) Mary Flahive and John Lee give tips on how to teach induction. For a variety of reasons, they encourage professors to downplay proofs of theorems such as the “baby Gauss” formula

\displaystyle\sum_{k=1}^n k=\frac{n(n+1)}{2} for all n\ge 1.

Indeed, I have noticed that students can master such proofs pretty quickly, yet not really understand proofs by induction. The proofs of sum and product formulas are pretty mechanical: prove the base case P(1), state the inductive hypothesis P(k), write the sum/product for the case n=k+1, pop off the k+1st term, substitute the n=k formula, and do a little algebra to prove P(k+1). All the problems look the same and they figure out the pattern pretty quickly.

Then in later courses they have lot of difficulty with proofs by induction.

This semester I decided to teach induction differently (I was teaching Discrete Mathematics, our gateway course to the mathematics and computer science majors). I started with sum/product proofs, but quickly moved on to other examples that were not of this standard type. Here are some that I gave.

1. Interval of integers. An interval of integers is a set of the form ~[a,b]=\{a,a+1,...,b-1,b\}\subset\mathbb{Z} (where a\le b). If I is an interval of integers containing n elements, how many subintervals does it contain? Prove your result using induction.

2. Matchstick squares I. It is possible to make a square with four matchsticks and to make two adjacent squares using seven matchsticks. How many matchsticks does it take to make line of n squares? Prove your result using induction.

3. Matchstick squares II. In the example above define a joint to be a spot where two or more matchsticks meet. One square has four joints and two squares have six joints. How many joints will n adjacent squares have? Prove your result using induction. (I had them do (2) for homework and put (3) on their exam.)

4. Trominoes. Start with a board consisting of an n\times n grid of squares and a pile of trominoes (el-shaped pieces that cover 3 squares each). Pick any square on the board and color it black. The question is: is it possible to tile the entire board except the blackened square with trominoes? The answer, in general, is “no.” Find a counterexample. However, if the board is 2^k\times 2^k then it is always possible. Prove this by induction. (Here are some printable trominoes puzzles and pieces. Here is a Trominoes applet to play with.)

5. Let us teach guessing. I spent one class showing George Polya’s 1965 video Let us Teach Guessing (now out on DVD). Polya leads his class through a discussion of the question: five planes divide space into how many regions? It is a fascinating problem with a surprising conclusion. At the end of the video the students know the answer to that question and can find the number of regions into which n planes divide space. For homework I have them prove this result. I was inspired to try this by David Bressoud who wrote about it in his Launchings column for the MAA.

It was really enlightening to grade these problems. For example, for the matchstick problem, many of the students wanted to give a purely algebraic proof—one that never referred to the matches at all. They applied their formula in the base case and said it worked without talking about how many matches it takes to make a single square. Then they tried to prove the inductive case without ever referring to a line of k or k+1 squares—they wanted to do it purely from the equations. When I spoke with them about it afterward they said that they didn’t think that the matches and squares were mathematical enough, but the algebra was. Another group of students proved the inductive case “backward”—they started with the formula for n=k+1 and tried to conclude something about the squares.

By the end of the unit on induction they seemed to have a pretty good grasp of the proof technique. I’m curious to see how well this group of students will do as they go through the major.

1 Comment

Posted in Math, Teaching | Tags: , , , , , , , ,

Posted by: Dave Richeson | October 20, 2009

Kindergarten Mathematics (part 2): a report

Last week I wrote a blog post asking for suggestions for math to present to my son’s kindergarten class. My readers posted many great comments. Thank you all.

Today was the big day,… and it was a great success!

I began by talking about what I do. My son introduced me as a math teacher. I asked if anyone knew the “big name” for a math teacher. One of the other kids said mathematician, which impressed me (even though her mother is also a mathematician at my college). I told them that I had two main jobs: teaching math and doing research to try to discover new math that no one else had ever thought of before. We talked a little bit about what math is: numbers, patters, shapes, puzzles, etc.

Then I told them I had two activities.

Activity #1. Tricky sequences.

This one I stole almost completely from this wonderful post at the Math With My Kids blog. You can read his blog for more details, but here it is in a nutshell.

At home I wrote three sequences on piece of poster board and covered the numbers with Post-It notes (actually, you could see the numbers through the Post-Its, so I put decorative stars on them to obscure the view).

In the class I had my son pull the Post-It notes off one-at-a-time while the kids guessed the next numbers in the sequence. The sequences I used were:

1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 3 1 2 1 4 1 2 1 5 1 2 1
1 1 1 3 1 4 1 1 3 6 1 1 3 1 4

Here’s the trick with the last one. Start with 1 and ask them what they see.  One. How many ones? One. OK, you see one one—then I peel off the 1 1. Now what do you see? Three ones. I peel off 3 1. Now what do you see? Four ones and one three. 4 1 1 3. etc. It was tricky, but I really think that they got it (or some of them did). Taking MWMK’s suggestion I asked them, if they thought that there would eventually be a 5, or a 10, or 100, or 1000000, etc. I told them that I didn’t know and that maybe no one knew, but these are the kinds of questions that mathematicians ask. And it is their job to see if they can answer them.

The kids seemed to love this activity. They were shouting out the next numbers at the top of their lungs. The teacher did a great job of occasionally bringing them back under control without squashing their enthusiasm.

Then I passed out a marker and a strip of paper with 8 boxes in a row to each student (actually, my son passed them out—he loved being my assistant). I asked them to write down the first 8 terms in a sequence that had some pattern—they could make it any pattern they wanted. After they were done I took volunteers to share their sequences. It turned out that almost everyone wanted to show off their pattern.

Activity #2: The Ringmaster’s Dilemma

This activity is based on an old (it dates back to at least 1882) magic trick that has been called the “Afghan Bands.” (I wrote about it in my book, p. 163, if you are interested.)

The circus is coming to town and the ringmaster accidentally left behind a trunk that had some of the circus equipment. He needs the following things in order for the circus to be able to run.

  1. Harnesses for the two trapeze artists.
  2. A giant collar for the fierce lion (in the original it was a belt for the fat lady).
  3. Collars for the two-headed dragon (in the story it was belts for the Siamese twins).
  4. A decorative belt for the dancing elephant (this wasn’t in the original story).

I held up the picture below with the needy circus stars.

circusanimals

Because his trunk was missing, all the ringmaster had at his disposal were three belts (made from strips of paper taped end-to-end: one with no twists, one with a half twist, and one with two half twists) and a small rectangular piece of fabric (an index card).

Fortunately for the ringmaster, the mathemagician Isaac Newtini was traveling with the circus. I held up a poster made using the trick in this video. (To make the poster yourself, download this pdf, print it double sided, trim 1/4″ off each edge, cut along the lines, fold as in the video, and tape onto colored paper with 1/4″ margins.)

circusposter1 circusposter2

The ringmaster asked Isaac Newtini if he could turn these four objects into the objects he needed. The mathemagician said he could.

I had made all three types of twisted bands the night before. They were made with long thin paper and had the midlines drawn on them to guide the kids’ cutting (to get the full effect, the Möbius bands had a line drawn down both sides of the strip before taping). I put a little cut in the midline so that the kids could insert their scissors and start their cutting easily. I put 1’s on the untwisted bands, 2’s on the Möbius bands (with one half-twist), and 3’s on the bands with two half twists.

My son passed out pre-made versions of all three types of twisted bands to the class (one to each student) along with scissors.

I asked the 1’s to hold up their hands. I asked them what they thought would happen when they cut down the middle. They all said that they would get two bands. They did the cutting, and found that they were correct. These were the harnesses for the two trapeze artists.

Then I asked the 2’s what they thought would happen when they cut their bands down the midline. They gave the same answer as the 1’s did. (By the way, I told them that their object was called a Möbius band.) But when they cut down the midline they discovered that they still had one loop, now twice the length. (The gasp of shock that came out of many of their mouths—especially the teacher’s—was priceless.) This is the collar for the lion.

When I asked the 3’s what they thought would happen, I got many different answers. When they did the cutting they found out that it produces two bands linked together—for the two-headed dragon.

Finally, we came to the dancing elephant. I asked if they had any ideas how we could make a big decorative belt using only the index cards. One child suggested cutting it into thin strips and taping them together—a brilliant idea, I thought—but unfortunately, I told her, we used up all the tape making the bands. Instead, I used this trick to show them that you could turn an index card into a decorative belt for an elephant. I put the finished product around my son’s waist.

I ended by giving them uncut versions of the Isaac Newtini poster and suggested that they try to cut them and fold them to look like the poster (I showed them why the poster was so weird).

Overall this was a great experience. I could tell my son was extremely happy that I came in to talk to his class. The kids seemed to have fun. And, my son’s teacher loved the lessons. She asked me if I could come back another time this year to present another math activity.

The whole presentation took about 35-40 minutes.

3 Comments

Posted in Math, Teaching | Tags: , , , , ,

Posted by: Dave Richeson | October 16, 2009

Mathematical art by Kevin Van Aelst

I just stumbled upon the website of the artist Kevin Van Aelst. His photographs are scenes constructed from food and drink that take the form of mathematical and scientific images.

Here are some of the mathematical pictures on his artwork page:

Leave a Comment

Posted in Math | Tags: , , , , , , ,

Posted by: Dave Richeson | October 12, 2009

Kindergarten mathematics

This is a call for help. My son’s kindergarten teacher has invited parents to come in and talk about their careers. I’d like to go in and talk about math. I’d like to have some interactive hands-on mathematics activities for the kids to do. I also want them to be activities outside the typical kindergarten curriculum. [Update: my math lesson has already happened. Read about it here.]

Do you have any suggestions? If so, please leave them in the comments below.

I have no expertise in childhood development, but here are some of the facts I’ve observed based on the abilities of my son and his friends.

  • Most of the kids are 5 years old (a couple are 6).
  • They can count, but they don’t necessarily know any arithmetic (although some do).
  • They know the alphabet, but they can’t read or write except maybe the most basic words (such a their names).
  • They can’t draw very well (eg. straight lines, circles, etc.).
  • They can uses scissors, tape, glue, staplers, etc., but their accuracy is not great.
  • They can do some simple logical reasoning.
  • They have short attention spans.

Here are some ideas that I came up with. (Some of these were suggested by my colleagues and my followers on Twitter.) This list is the result of a brainstorming exercise, so I know that some ideas are half-formed and some are too advanced for this age group, but I still kept them on the list.

Paper folding, cutting, taping

Bubble activities

Geometry

Pattern recognition

  • Teach them the game Set
  • List three things in a sequence, ask for the fourth (for example, a picture of a triangle, a square, and a pentagon)
  • What do these have in common?

Drawing and coloring

  • Simple bridges of Königsberg/graph tracing problems
  • 4-color theorem
  • Coloring patterns in square, triangular, hexagonal graph paper

Counting

  • Permutations (using a tree): We have 3 pairs of shoes, 4 shirts/dresses, and 3 hats. How many outfits are possible?
  • Rock-scissors-paper tournament

Numbers

Stick puzzles

Knot theory (some of these are definitely too advanced)

  • Have everyone stand in a circle with hands thrust toward the center of the circle. Have the children grab random hands. The result is a giant human knot or link. Have them unknot themselves by taking turns letting go, changing a crossing, and grabbing hold of their partner’s hand.
  • Take a long string and tie the ends around Alice’s wrists. Bob’s hands are tied together in a similar way, except his string passes through the loop made by Alice’s arms and her string. Can they become disentangled without pulling the looped string off their own hands?
  • Alice holds a long unknotted string with one free end in each hand. Can she hand the string to Bob (one end to one hand, the other end to his other hand) so that when he receives it it is knotted?
  • Charley is wearing a big, baggy t-shirt. He clasps his hands in front of him. Can Alice and Bob take off and manipulate the shirt so that it goes back on Charley inside out without Charley unclasping his hands?
  • Bob is wearing a big, baggy t-shirt. He stands face-to-face with Alice and holds her hands to form a circle. Can Charley take the shirt off of Bob and put it on Alice without them letting go of their hands?
  • Tie three strings to a chair. Braid them together in any way (no knots though!) so that the left strand ends in the left position, the middle one in the middle, and the right-most one on the right. Tape the free ends together. Figure out how to unbraid it without untaping the ends. (It is always possible.)

Play dough/clay

  • Turn a coffee cup into a donut without breaking a loop

19 Comments

Posted in Math, Puzzle, Teaching | Tags: , , , , , , , , ,

Posted by: Dave Richeson | October 6, 2009

Tennenbaum’s proof of the irrationality of the square root of 2

Yesterday I came a across a new (new to me, that is) proof of the irrationality of \sqrt{2}. I found it in the paper “Irrationality From The Book,” by Steven J. Miller, David Montague, which was recently posted to arXiv.org.

Apparently the proof was discovered by Stanley Tennenbaum in the 1950’s but was made widely known by John Conway around 1990. The proof appeared in Conway’s chapter “The Power of Mathematics” of the book Power, which was edited by Alan F. Blackwell, David MacKay (2005).

It is a proof by contradiction. Suppose \sqrt{2}=a/b for some positive integers a and b. Then a^2=2b^2=b^2+b^2. Geometrically this means that there is an integer-by-integer square (the pink a\times a square below) whose area is twice the area of another integer-by-integer square (the blue b\times b squares).

sumsquares

Assume that our a\times a square is the smallest such integer-by-integer square.

Now put the two blue squares inside the pink square as shown below. They overlap in a dark blue square.
nestedsquares

By assumption, the sum of the areas of the two blue squares is the area of the large pink square. That means that in the picture above, the dark blue square in the center must have the same area as the two uncovered pink squares. But the dark blue square and the small pink squares have integer sides. This contradicts our assumption that our original pink square was the smallest such square. It must be the case that \sqrt{2} is irrational.

[Note: the squares in the pictures almost work. They are 17\times 17 and 12\times 12. As Conway points out, 17^2=289\approx 288=2\cdot 12^2. Indeed \sqrt{2}=1.4142\ldots\approx 1.41666\ldots=17/12.]

If you want to see more examples, look at Miller and Montague’s paper “Irrationality From The Book.” They extend this idea to give geometric proofs that \sqrt{3}, \sqrt{5}, \sqrt{6}, and \sqrt{10} are irrational.

Also, Cut-the-Knot has 19 proofs of the irrationality of \sqrt{2} (including this one).

5 Comments

Posted in Math, Teaching | Tags: , , , , , ,

Posted by: Dave Richeson | October 4, 2009

A new way to collaborate: DropBox

logoI have a long-time collaborator who lives in Georgia (I’m in Pennsylvania). I’ve had good luck collaborating with him via email, but it is a pain. As soon as one of us edits a file he sends it to the other person as an email attachment. We haven’t had any “forked” files, but we do always have to take turns editing and we have to be good about remembering to send files immediately after they are modified.

Now we’re applying for a grant with a third person who lives in Virginia. Collaborating with three people in three different states is sure to be even more of a challenge. (It was a challenge even passing the grant proposal around.)

If we weren’t mathematicians, then Google Docs or the forthcoming Office Web might be good options for collaborative writing. But we write everything in LaTeX, so these options don’t make sense. I tried MonkeyTex, a site like Google Docs but which compiles LaTeX documents and produces pdf documents. It is a really cool idea, but I didn’t want to give up my trusty desktop apps: TexShop and BibDesk. (Plus, MonkeyTex seemed like a small operation and I didn’t know if I should trust them with my files—even big shots like Google and Facebook have had downtime issues recently.)

This week I think I found the perfect solution: DropBox. DropBox is touted as an online backup system or an online storage space, but it is so much more. Basically it works like this. You sign up for an account with 2 GB of FREE online storage and it creates a folder on your computer (an actual folder, not a link to a folder in the clouds somewhere). Then any time you add, delete, or change a file in this folder, it automatically syncs it with the cloud.

That’s cool, right? We’re just getting started. If you have several computers, you can put a DropBox folder on those too, and all the folders on all of your computers remain in sync—even if you have one Mac, one PC, and one Linux computer. Files can also be accessed via the DropBox website or with your iPhone/iPod Touch.

Again, this is what I like: when you are working on your computer—adding, deleting, modifying, and LaTeX-ing these files—you won’t be able to tell that anything is happening. They are ordinary local files behaving as usual. But DropBox is syncing them behind the scenes.

Now how does this help collaboration? You can share folders within your DropBox folder. What that means is that each person who is sharing a folder will have the identical folder in their DropBox folder. So any changes made by one person will appear in the folder of every other person! Brilliant! Just what I wanted.

As an added bonus, DropBox stores past versions of files. If one of your collaborators messes up a file, you can go online and look at the history of the file and revert back an earlier version.

One downside is that there are no safeguards to prevent two users from editing a file at the same time. But if two different copies of the same file are saved, then two versions will appear in the shared folder. The users would have to work on merging the documents by hand.

I’m planning to use DropBox in my teaching too. Next semester I’ll be teaching topology. I teach it using the “Moore method.” The students are given a skeleton of a textbook (in LaTeX) and they must prove all of the theorems, work out all of the examples, and type them into the class textbook. There is a rotating “secretary” position and a rotating group of “editors.” Sharing the files has always been a hassle. The first time we passed around a disk with the files, the next time each person emailed the file to the next person on the list, and the last time I set up a class Gmail account. The logistical issues were a pain to deal with. This time I will have each student get a DropBox account, and we will have one shared folder with the textbook in it—that’s going to be so much easier!

If you are interested in trying DropBox, follow this link. Doing so would give me credit for “referring” you. Both you and I will get 250 MB of additional storage (up to 3 GB). If you would rather not do that, go directly to the DropBox website.

13 Comments

Posted in Academic Technology, Math, Teaching | Tags: , , , , , , ,

Posted by: Dave Richeson | September 29, 2009

Bolzano-Weierstrass rap

In my next real analysis lecture we’ll be discussing the Bolzano-Weierstrass theorem. (It says that any bounded sequence of real numbers contains a convergent subsequence.)

I’ll be showing my class this video in which Steve Sawin (AKA Slim Dorky) raps the complete proof of the theorem.

You can read the lyrics here.

He has some other songs and videos on his website.

Leave a Comment

Posted in Humor, Math | Tags: , , ,

Posted by: Dave Richeson | September 27, 2009

Is or an inclusive or or an exclusive or

(That was a fun title to write!)

At the start of our discrete mathematics course we talk about symbolic logic. Students are often confused by the logical operator “OR.”

If p and q are statements then p OR q is true if either p is true or q is true or if both p and q are true. This is easily expressed in a truth table:

p q p OR q
T T T
T F T
F T T
F F F

The reason this confuses students is that sometimes when we say “or” in everyday conversation we mean p is true or q is true, but p and q are not both true. (For example, “the door is open or the door is closed.”)

This brings to mind the logical operation exclusive or, “XOR” (the usual “or” is inclusive or). The truth table for XOR is shown below.

p q p XOR q
T T F
T F T
F T T
F F F

It seems like we use “or” as exclusive sometimes and inclusive other times.

My colleagues and I were talking about this at the lunch table the other day. One of my colleagues presented a simple example that illustrates this confusion.

Waiter: “Would you like tea or coffee?” (exclusive or)

Patron: “Coffee, please.”

Waiter: “Would you like cream or sugar?” (inclusive or)

Patron: “I’d like both, thank you.”

I thought this was a great example.

Another one of my lunchmates is a linguist and he asserted that when we say “or” we always mean inclusive or—even though it seems that we’re using exclusive or. For example, the patron above could have asked for both coffee and tea, it is just that that isn’t usually done.

What about the door being open/closed example? A door can’t be both open and closed. In particular, ”the door is open” and “the door is closed” can’t both be true at the same time. But this doesn’t mean that that use of “or” is exclusive or. Exclusive or means that when both statements p and q are true, p XOR q is false. In the door example, we never encounter the “true or true” situation!

According to Wikipedia the source of this argument is a 1971 article by Barrett and Stenner called “The Myth of the Exclusive ‘Or’” (Mind, 80 (317), 116–121).

No author has produced an example of an English or-sentence that appears to be false because both of its inputs are true. Certainly there are many or-sentences such as “The light bulb is either on or off” in which it is obvious that both disjuncts cannot be true. But it is not obvious that this is due to the nature of the word “or” rather than to particular facts about the world.

Update: I had another example to illustrate this misconception. The sentence

x<0\text{ OR } x\ge 0,

is true for all x, right? And this is the logical (inclusive) OR, right? But this is exactly the same as “the door is open or the door is closed.” Just as the door is either open or closed, but can’t be both open and closed, one of the two inequalities x<0 and x\ge 0 must be true, but both can’t be true simultaneously. The fact that both halves can’t be true at the same time (mathematically) doesn’t mean that two trues joined by this “or” is false.

Leave a Comment

Posted in Math, Teaching | Tags: , , ,

Posted by: Dave Richeson | September 22, 2009

An applet for teaching the limit of a sequence

I’m currently teaching real analysis. Right now we’re discussing limits of sequences. The definition is:

The limit of a sequence (a_n)_{n=1}^\infty is L (or converges to L) if, given any \varepsilon>0, there exists a natural number N such that |a_n-L|<\varepsilon for all n\ge N.

I used GeoGebra to create the following java applet, which illustrates the definition of a limit. (Clicking on the previous link or the picture below will open the applet in a new window.)

Picture 2

2 Comments

Posted in Academic Technology, Math, Teaching | Tags: , , , , ,

Posted by: Dave Richeson | September 18, 2009

LaTeX now available in Google Docs

Google Vice President and Chief Internet Evangelist (yes, that is really his title) and inventor of the internet Vint Cerf visited our campus a couple of years ago. At one point he asked about what people wanted from Google. I said that I would love a Google Docs/LaTeX mashup. How great would it be for mathematicians to collaborate on LaTeX documents on Google Docs? I can’t tell you how much I would love that.

So maybe you have me to thank for this news (har har har): Google Docs now has limited LaTeX integration. Now, it isn’t exactly what I asked for. You aren’t writing LaTeX documents. They have it set up like a word processor, with an “insert > equation…” menu item. It gives you a pop-up window and in it you can type LaTeX code (screenshot below). It shows you the corresponding mathematical formula and allows you to insert it into the document as an image. If you need to edit the formula later you can double-click the image and it will send you back to the pop-up window.

Picture 1

I just tried it out and found it to be usable. I can imagine getting frustrated every time I have to go to the pull-down menu, rather than typing LaTeX code straight into the document, but it is a step in the right direction.

In case you want to give it a try and don’t have a Google Docs account, I’ve set up a sandbox for you to play in. Edit to your heart’s content (just keep everything G or PG, please). As with other Google Docs, you can also publish your work as a web page.

I’m still hoping that they will get true LaTeX integration, but it will probably never happen. This is a neat feature, but I won’t be able to use it for professional collaboration.

3 Comments

Posted in Academic Technology, Math | Tags: , ,

Older Posts »

Categories