I like the Fibonacci sequence as an example for induction and recursion. It has an interesting structure, beginning with two base cases in its definition: F(0) = 0, F(1) = 1, and for n> 1, F(n) = F(n-2) + F(n-1).
The sequence is rich in properties. There are hundreds of connections between elements of the Fibonacci sequence. One such connection is that the sum of the Fibonacci numbers from 0 to n is F(n+2) - 1. Now here's where things take a strange turn.
The natural way to prove properties about a sequence defined recursively (read inductively) is using induction. To prove the above property, you need just one base case: the sum of the Fibonacci numbers from F(0) to F(0) is F(2) - 1 (check my calculation). The rest of the proof follows by simple induction. Assume that n is a generic natural number, and that the sum of the Fibonacci numbers from 0 to n is F(n+2)-1. Then the sum of the Fibonacci numbers from 0 to n+1 can be partitioned into the sum from 0 to n --- by assumption this is F(n+2) - 1 --- plus F(n+1). Adding these two terms yields F(n+3)-1, which verifies that the result for the Fibonacci numbers from 0 to n+1 follows from the result from 0 to n.
So, the result is true for every natural number n. Strange that when the definition of F(n) requires two base cases, proving this property requires just one.
Monday, September 29, 2008
Friday, September 26, 2008
Hex(agons), lies, and ternary trees
A handful of interesting trends emerged this week, and the overhead projector reminded me of its vulnerability to overheating (and, thus, under-lighting).
At this point in the course, I use the technique of simple induction to lie to my students in three different ways. My motivation is to vaccinate them against false proofs by letting them work through a few. Both the evening and day section seemed to spot the sleight-of-hand fairly readily. Although it's not meaningful to generalize, perhaps this cohort of students has its BS-detector cranked up higher than previous cohorts, or I'm a worse liar than I once was.
In another thread, a challenging (I think) counting problem that isn't due for a month has generated enough controversy about the number of distinct ternary trees with five nodes that I've had to resort to writing a short program to convince myself of the correct answer. I'm curious to see whether my students begin to use their programming language of choice to explore questions, and whether this hides or obscures the connection between programs and proofs.
In lecture, one student brought out the subtle point of whether we can really assume we have a full binary tree with n+1 nodes if such a configuration is impossible. She noted that in some cases (when n+1 is even) there will be no such FBTs. What makes this situation interesting is thiat it corresponds to vacuous truth --- of there are no FBTs of size n+1, then any claim about them is true (they have n edges), so the only case where there's work to do is in the case where there [b]is[/b] a FBT of size n+1.
At this point in the course, I use the technique of simple induction to lie to my students in three different ways. My motivation is to vaccinate them against false proofs by letting them work through a few. Both the evening and day section seemed to spot the sleight-of-hand fairly readily. Although it's not meaningful to generalize, perhaps this cohort of students has its BS-detector cranked up higher than previous cohorts, or I'm a worse liar than I once was.
In another thread, a challenging (I think) counting problem that isn't due for a month has generated enough controversy about the number of distinct ternary trees with five nodes that I've had to resort to writing a short program to convince myself of the correct answer. I'm curious to see whether my students begin to use their programming language of choice to explore questions, and whether this hides or obscures the connection between programs and proofs.
In lecture, one student brought out the subtle point of whether we can really assume we have a full binary tree with n+1 nodes if such a configuration is impossible. She noted that in some cases (when n+1 is even) there will be no such FBTs. What makes this situation interesting is thiat it corresponds to vacuous truth --- of there are no FBTs of size n+1, then any claim about them is true (they have n edges), so the only case where there's work to do is in the case where there [b]is[/b] a FBT of size n+1.
Friday, September 19, 2008
Ah yes. Time flows differently through different parts of a schedule.
Three fifty-minute lectures spread over Monday, Wednesday, and Friday seem to fit a topic, and the mood of a section, completely differently from the "same" 150 minutes spread over a single 6 to 9 pm interval. The length of time a given topic takes, and the engagement of the students seems to be completely elastic, depending on the time of day. Although there are questions, discussion, and argument in both instances, in the evening version of 150 minutes I feel as though there are some for whom the details of complete induction are an irritating distraction from world 'o warcraft or urgent discussions with a neighbour.
Complete induction. This seems to be the flavour of induction where the character of base cases comes into focus. Since a valid proof by complete induction doesn't require any base cases, and doesn't really provide a template for the sort of values you should assume are base cases, you're forced to think about which natural numbers n can have P(n) established about them without referring to any smaller natural number (induction free!), and which require the helping hand of an induction hypothesis.
Three fifty-minute lectures spread over Monday, Wednesday, and Friday seem to fit a topic, and the mood of a section, completely differently from the "same" 150 minutes spread over a single 6 to 9 pm interval. The length of time a given topic takes, and the engagement of the students seems to be completely elastic, depending on the time of day. Although there are questions, discussion, and argument in both instances, in the evening version of 150 minutes I feel as though there are some for whom the details of complete induction are an irritating distraction from world 'o warcraft or urgent discussions with a neighbour.
Complete induction. This seems to be the flavour of induction where the character of base cases comes into focus. Since a valid proof by complete induction doesn't require any base cases, and doesn't really provide a template for the sort of values you should assume are base cases, you're forced to think about which natural numbers n can have P(n) established about them without referring to any smaller natural number (induction free!), and which require the helping hand of an induction hypothesis.
Friday, September 12, 2008
Start of CSC236, for fall 2008
Three lectures in to the Principle of Simple Induction, and I've learned a few things.
First, there seems to be no ideal medium for expressing mathematical ideas live to a large group of people. Slides are too canned --- they give the harmful impression that mathematics is completely clean and slick. Blackboards are volatile (your work is gone next lecture), and often suffer from poor lighting and the obscuring effects of chalk dust. Typing live in a mathematical editor such as Lyx doesn't make drawings or diagrams easy, and it still makes the math look too slick. And my latest toy, a tablet, is a bit strange to write legibly on, and I live in fear of losing my stylus.
Second, examples that I begin by thinking will illustrate one feature sometimes turn out to illustrate another.
For example, my gut reaction to the claim that for every natural number n, 3 raised to the power of n will end with unit digit either 1, 3, 7, or 9, was that here is a case that will likely require multiple base cases. As I began to sketch a proof in my head, I realized that all that's required is the case for n=0.
Similarly, some colleagues had once assigned the question "How many odd subsets does a set with n members have?" as a typical exercise in induction. I brainstormed this with one section, and the conjecture that there were (2^n)/2 odd subsets emerged. The case where n=0 seems like a special case, since the empty set has an even subset (itself) and no odd subsets, whereas for other values of n there seem to be the same number of even and odd subsets.
One student firmly defended her position that no special treatment is required for n=0 --- the induction step only needs to use that fact that there is a 1-1 correspondence between the even subsets of S\{x} and the odd subsets of S, and a 1-1 correspondence between the odd subsets of S\{x} and the odd subsets of S. I was very skeptical at first, and then I realized that her argument meant that no induction was needed --- the set of odd subsets of a set with n members can be put in 1-1 correspondence with the set of all the subsets (odd and even) of a set of n-1 members.
So, although induction would work as a proof technique, it was not required.
First, there seems to be no ideal medium for expressing mathematical ideas live to a large group of people. Slides are too canned --- they give the harmful impression that mathematics is completely clean and slick. Blackboards are volatile (your work is gone next lecture), and often suffer from poor lighting and the obscuring effects of chalk dust. Typing live in a mathematical editor such as Lyx doesn't make drawings or diagrams easy, and it still makes the math look too slick. And my latest toy, a tablet, is a bit strange to write legibly on, and I live in fear of losing my stylus.
Second, examples that I begin by thinking will illustrate one feature sometimes turn out to illustrate another.
For example, my gut reaction to the claim that for every natural number n, 3 raised to the power of n will end with unit digit either 1, 3, 7, or 9, was that here is a case that will likely require multiple base cases. As I began to sketch a proof in my head, I realized that all that's required is the case for n=0.
Similarly, some colleagues had once assigned the question "How many odd subsets does a set with n members have?" as a typical exercise in induction. I brainstormed this with one section, and the conjecture that there were (2^n)/2 odd subsets emerged. The case where n=0 seems like a special case, since the empty set has an even subset (itself) and no odd subsets, whereas for other values of n there seem to be the same number of even and odd subsets.
One student firmly defended her position that no special treatment is required for n=0 --- the induction step only needs to use that fact that there is a 1-1 correspondence between the even subsets of S\{x} and the odd subsets of S, and a 1-1 correspondence between the odd subsets of S\{x} and the odd subsets of S. I was very skeptical at first, and then I realized that her argument meant that no induction was needed --- the set of odd subsets of a set with n members can be put in 1-1 correspondence with the set of all the subsets (odd and even) of a set of n-1 members.
So, although induction would work as a proof technique, it was not required.
Subscribe to:
Posts (Atom)
