[Wonderful discussion going on in the comments dealing with math terminology and the underlying concepts embedded here. As always, my post is just the appetizer. The main course is to be found in the comments section. If you enjoy this discussion you may also want to visit some of my recent posts touching on Singapore Math and a review of an important book by Alec Klein on teaching gifted children.]
The following is similar to a question that appeared on the PSAT a couple of years ago. The College Board has been testing recursively-defined sequences for some time. Students take the test, then it's 'out of sight, out of mind'. Educators may want to explore the ideas behind these problems in much greater depth. Recursive sequences are an important topic and are now included in many sets of standards. Should this be viewed as exclusively a high school topic?
Consider the sequence 11,6,5,... defined as follows:
Each term after the second is the nonnegative difference of the two preceding terms.
What numbered term has a value of zero?
Things to ponder beyond the answer...
(1) Is this question appropriate for middle schoolers?
(2) Would the terminology nonnegative difference be problematic for some students?
Note: This is the actual wording from the exam. Would you have reworded this using absolute values?
(3) If an educator wants students to develop these ideas in a more extended investigation, how much preliminary groundwork needs to be laid if any? It's important for our students to understand that mathematical researchers often start with specific examples like this without knowing the general relationship. They analyze many specific examples looking for patterns just like students can be trained to do.
(4) How many particular examples would students need before they can begin to formulate an hypothesis? Should the first two terms be restricted to positive integers (or even integers for that matter!)? Should the instructor suggest different starting values or allow the students to explore? As always, the issue is the role of the instructor while students are exploring. Teachers inexperienced with facilitating these kinds of investigations can benefit from observing those who have been doing this for awhile. It ain't obvious and it sure ain't easy!
(5) Would most students conjecture that the sequence will eventually become 'stable' at some point if the initial two terms are integers? Would middle schoolers be able to explain why this would happen?
(6) Do you think some students would be able to formulate a general theory for this type of sequence? Develop a formula for the number of terms required for the terms to reach zero? How many students in middle school or high school would suggest starting with decimals or even irrational numbers like pi? Is there ever an end to these investigations?
Well there is an end to this post! [Notice that the original question seems less significant now.]
Wednesday, August 22, 2007
How Recursion is Tested on the SATs and much more...
Subscribe to:
Post Comments (Atom)
Posts
9 comments:
I want to try this one. But the "nonnegative difference" phrase would be a problem that I foresee. Even I began thinking that the difference of the two proceeding numbers had to be not negative; and then you may reach zero at some point but I didn't (10 terms). Then I realized what it meant: and I got to zero easily.
But this was good, for all sorts of reasons, for the beginning of school. I'll try to let you know what happens. (I will probably let the kids decide what "nonnegative difference" means).
"Positive Difference" comes up in MATHCOUNTS problems quite a bit, so I think my middle schoolers who have been exposed to that, if they remember what that meant, might be able to deal with "non-negative difference".
As to whether middle schoolers will predict that the sequence will always stabilize, I'd say probably not, at least not without trying a bunch of examples first. Even less likely is that they would be able to explain why, though with enough experience with examples, they might have a vague notion that they couldn't explain clearly. ;-)
I might try this with my group in September as well. I have a lot of things bookmarked here to try with them at some point...
Thanks!
Hmm, personally I would have worded it as absolute value...I wonder how that would change the understanding of the problem. I think it would make it "easier' - I wonder what h.s. students would think?
I don't like this as an SAT question. It tests the ability to mechanically understand the wording of the question, which is good. It tests perseverance, which can be counterproductive on a timed test. It tests the ability to do arithmetic fast, but shouldn't they know that already?
The interesting question for the classroom is this: find an efficient proof that the sequence eventually has a 0 value, and therefore becomes a, 0, a, 0, … I like this way:
Call the sequence x_1, x_2, x_3, …
Then, x_3 = |x_1 - x_2| < max (x_1, x_2) unless one of them is zero.
x_4 = | x_2 - x_3| < max(x_2, x_3).
If x_2 is larger, x_4 ≤ x_2 - 1. If x_3 is larger,
x_4 ≤ x_3 - 1 < max(x_1, x_2) - 1.
We can crunch this down to
x_3 and x_4 ≤ max(x_1, x_2) - 1 unless the sequence hits zero.
But the form of the sequence is the same whether wherever we start at the first term or the third, or the fifth. So,
x_5 and x_6 ≤ max(x_3, x-4) - 1 ≤ max(x_1, x_2) -2, or the sequence hits zero.
Now, use mathematical induction.x_{2n+1} and x_{2n+2} are both ≤ max(x_1, x_2) - n, unless the sequence hits zero.
You can tell the students that this proof isn't very efficient; for the sequence in the SAT problem, this says you need to go at most 24 terms to reach zero, when you only need 10. But, efficiency isn't necessarily the aim of pure mathematics.
Then, you can explain the related proof idea of reductio ad absurdum, and give as an example Fermat's original proof of his conjecture for exponent 4: he showed that if you found x, y, and z such that x^4 + y^2 = z^4 ( a more general equation than the original--ask the students why!) then there were smaller positive numbers X, Y, and Z satisfying the same equation. But, you can only go down so far!
I had a feeling this question would generate some strong reactions!
Understanding the terminology was definitely part of what was being tested. This could have been clarified by an example, something often done on standardized tests, but not in this case. However, some of the students (again, a strong group) got past the wording, persevered through the algorithm and ended up with the result:
11,6,5,1,4,3,1,2,1,1,0
They didn't complain about having to go that far out. When I asked if they thought it would never reach zero, a student replied, "No, the numbers were getting smaller." No rigorous proof just good basic instinct. She didn't explain that the fact that the numbers were positive integers had a lot to do with this, but she didn't need to at that moment. It was up to me to probe further. I liked that very much. I did ask if anyone thought that reaching zero might depend on the original two numbers and someone suggested decimals (I thought they would suggest much larger integers):
0.45,0.11,0.34,0.23,0.11,0.12,0.01,
0.11,0.10,0.01,0.09,0.08,0.01,...
At this point, someone commented this would end just as if we had started with 45,11,34,23,..
Great stuff, huh! Since I had many other problems to review, I invited students to 'gmail' me by midnight if they found an example that wouldn't ever reach zero. No replies of course!
(I was hoping (?) for pi,2,pi-2,4-pi,2pi-6,10-3pi,16-5pi,
... A decreasing sequence of positive numbers that 'approaches' zero but will it ever get there?)
Obviously, we don't have to pursue all aspects of this in a 40-60 minute period and many would argue we don't have time for any of these excursions at all. Perhaps it's only for the math team nerds like me, but is it?
Eric, as always you blow me away with your extensive knowledge and understanding of how one problem relates to so many others. I like the reductio ad absurdum argument, something our students would not often get to see, yet one of the more elegant methods of proof in mathematics. Nice to hear from you again!
I believe there is much more to say about this problem and the discoveries middle school and secondary students would make if given the opportunity to explore. How does one balance these benefits with the real issues of working through the curriculum. Again, I always thought of it as planting seeds. I would provoke them with this kind of question, then leave them hanging: "Sorry folks, you'll have to continue working on this outside of class. If anyone pursues it further, submit your findings. I will evaluate them and you can earn celebrity on my blog or bonus points whichever is more important to you!" They would take the points...
I would like some more thoughts on this question Definitely try it with different starting values (including negative positive integers) and see if you can relate your findings to Eric's abstract proof. Consider this:
100,13,87,74,13,61,48,13,35,22,13,9,
4,5,1,...
Note the subsequence of SEVEN terms: 100,87,74,61,48,35,22 ends in NINE. Now would some students, recognize that when 100 is divided by 13, the quotient is SEVEN and the remainder is NINE! There's still a lot more to say here. Don't stop - it could be worth millions of bonus points or celebrity and fame...
I think this is directly related to the standard algorithm for long division wherein we subtract the divisor once at a time.
Also, for some reason, my brain keeps saying Eulcid's algorithm.
TC
TC--
I 'totally' agree with you!
Repeated subtractions are equivalent to the basic division algorithm. You'd be amazed how many students aren't fully comfortable with this (Example: I have $1000 and, in a spirit of altruism, I decide to give $11 of this money repeatedly to perfect (or imperfect) strangers. How much money will be left over at the 'end?').
As I was analyzing this, I also kept thinking it's related to the Euclidean Algorithm, which is recursive and leads to the gcf of p and q:
p = 144; q = 64
144 = 64 x 2 + 16
64 = 16 x 4 + 0
Therefore, gcf(144,64) = 16 (last nonzero remainder).
It's weird we were both thinking of this, but then, weird minds think alike!
Yes, this is a slow way of doing Euclid's algorithm. Suppose the numbers are a and b for a >b, where a = qb + r, 0 ≤ r < b. Then, you get the sequence
a, b, a-b=(q-1)b + r, [and if q>1]
(q-2)b + r, b, [and if q>2]
(q-3)b + r, [and if q> 3]
(q-4)b+r, b, [and so on, eventually reaching]
b+r, r, b [and continue with this slow form of Euclid's algorithm.]
This would be much clearer to your students than my previous suggestion.
These books seem to be really informative for competitive exam preparation. Saw many LSAT Sample Questions online and even went through them thoroughly. One of the well-known online classes is providing budgeted sessions for law exam preparation too. Thinking to join them soon for best results.
Post a Comment