In continued tribute to Dr. Mandelbrot, here is a challenge problem for your Algebra 2 students which develops the ideas of iteration and recursively-defined sequences while providing technical skill practice. From my own experience, even some of the strongest will trip over the details so don't be surprised if you get many different answers for the 5th term in part (c) below! We all know that current texts do not provide enough mechanical practice and this becomes more evident as our top students move into the advanced classes.
THE CHALLENGE
A sequence is defined as follows. Each term after the first is two less than three times the preceding term.
(a) If the first term is 2, determine the 2nd through 5th terms.
(b) If the first term is 1, determine the 100th term. Explain.
(c) If the first term is x, determine simplified expressions in terms of x for the 2nd through 5th terms. To help you verify your answers, the 5th term is 81x - 80. Show all steps clearly. Compare your results with others in your group and resolve any discrepancies.
(d) Write a general expression for the nth term if the 1st term is x. It should work for all terms including the first! Explain your method. Proving your formula works for all n is optional.
Answer: 3^(n-1)x - (3^(n-1) - 1)
NOTE: Students who have learned the formula for the nth term of a geometric sequence should recognize the first term in this answer! Help them to make the connection...
(e) Extension: Change the recursive relationship to: Each term after the first is three less than twice the preceding term. Redo part (d) for this new sequence. The pattern is more challenging!
Ans: 2^(n-1)x - 3(2^(n-1) - 1)
NOTE: For the more advanced students, have them prove their "formula" by induction.
Final Comment: In what form do you think this kind of question would appear on the SATs and, yes, this topic is tested and has appeared!
"All Truth passes through Three Stages: First, it is Ridiculed... Second, it is Violently Opposed... Third, it is Accepted as being Self-Evident." - Arthur Schopenhauer (1778-1860)
"You've got to be taught To hate and fear, You've got to be taught from year to year, It's got to be drummed In your dear little ear. You've got to be carefully taught." --from South Pacific
Thursday, October 21, 2010
A Recursively Defined Sequence to Challenge Your Algebra Students
Subscribe to:
Post Comments (Atom)
Posts
4 comments:
I have a few comments, but one at a time. First, an infamous math puzzle.
The following riddle came up at a party once: Three sailors land a boat on an island; then, they gather coconuts for the rest of their voyage. When night falls, they prepare to sleep; they decide that each of them will keep watch for one-third of the night.
The first sailor stays up while the other two fall asleep. Now, these sailors have a somewhat peculiar sense of honor; the first decides to take and hide his share, so he takes the pile of coconuts, splits them into three equal piles with one left over, hides his third, and throws the one left over to a passing monkey.
When the second sailor takes his watch in the middle of the night, he too decides to take his share, and exactly the same thing happens; he splits the pile into three with one left over, hides his third, and gives the extra one to the monkey.
The third sailor in turn does exactly the same thing.
In the morning, the three sailors split the remaining pile, and toss the extra coconut to a passing monkey.
How many coconuts did they start out with?
The party-goers consider the question, and they make incorrect guesses. Finally, someone asks the mathematician who was watching the proceedings, and he says:
"There were -2 coconuts, of course."
"What?"
"Each sailor throws one coconut to the monket, leaving -3.
(It's a red herring that the story has the sailor splitting the coconuts into three piles with one left over first).
"Then, the sailor hides his share of -1 coconut, leaving -2 again.
"This happens three times in the night and once more in the morning. They started with -2 coconuts. and each one gets -1 coconut when they do the final split."
"But, they couldn't have collected a negative number of coconuts."
"You can add any multiple of 81 to the original number, and it will still work."
"Why 81?"
"Because 81 is 3^4. It can go through all the divisions and still stay a whole number."
(more later)
You see, fixed points are important. Fixed points of analytic functions and their iterates lead to Julia sets, and Julia sets lead to the Mandelbrot set. Look these up at MathWorld, please. The riddle I gave led to finding the fixed point of f(x) = 2/3 (x-1).
How would I introduce this to a HS student? I would lead quickly to part d, but I would make one slight notational change. When working with sequences like this, it is quite common to start indexing at 0. A power series is written as a_0 + a_1 (x-h) + a_2 (x-h)^2 + ...., and a sequence is b_0, b_1, ..., b_n, ....
So, let's look at properties held in common by all such sequences. Suppose sequences a_i and b_i satisfy the problem condition. Does the sequence (a_n + b_n) satisfy it? No: a_{n+1} + b_(n+1} = 3(a_n + b_n) - 4.
Does (a_n - b_n) satisfy it? No, but a_{n+1} - b_(n+1} = 3(a_n - b_n). That's an interesting relation all by itself, and easily solvable:
If a_n satisfies a_{n+1} = 3 a_n, then, a_n = 3^n a_0.
If a_0 = 0, then a_n = 0 for all n. Also, there is a sequence satisfying this rule with any value for a_0.
Note that this means that if two sequences a_n and b_n satisfy the recursion rule and a_0 = b_0, then the sequences are identical. All one need do is to find a single solution of the original recursion rule, and you can find all of them.
Does this remind any one of linear ODEs or linear systems of equations? Good.
So, is there the simplest of solutions for the original sequence, where c_0 = c_1 = c_2...? We find the fixed point of f(x) = 3x-2; it's 1. So, the sequence is of the form:
1 + b, 1 + 3b, 1 + 9b, ..., 1+3^n b, ......
The general solution is then
x=1+3^0 (x-1), 1+3^1 (x-1), ..., 1+3^n (x-1),....
Can we generalize this even more? Yes, with the hint of ODEs. This leads to the discrete calculus, which can be used to motivate differential calculus itself, but that will be in a later note.
Thank you for taking us "beyond."
The fixed point is so critical as you indicated. I was going to add an additional part and ask the more inquiring students to consider the general linear recurrence relation a_n=m(a_n-1) +b. What value of a_0 produces a fixed point. Also, for what value of m is there no fixed point?
You have to remember that our Alg 2 students see little of this other than the composition of a function with itself.
Thanks again for enriching my activity and relating it to Dr. Mandelbrot. As usual you are my mentor!
(continued)
I'm going to take my examples and notation from Concrete Mathematics, by Graham, Knuth, and Patashnik. That book is an extravagant source of examples and ideas that can be used at nearly every level of education, and it's beautifully typeset too.
The "finite calculus" or "discrete calculus" is an area of mathematics analogous to infinite calculus where one works with sequences and operators on them instead of functions and limits of difference quotients.
In calculus, you have the difference quotient: [f(x+h) - f(x)]/h. You take the limit as h goes to zero, and get the derivative of f. Most HS students aren't ready to see that.
But, what if you let h be 1? You get something you can apply to a sequence:
0, 1, 4, 9, 16, ..... transforms to:
1, 3, 5, 7, 9, ..... transforms to:
2, 2, 2, 2, 2,..... transforms to:
0, 0, 0, 0, 0, .....
If this process ever reaches all-zeroes, the original sequence came from a polynomial. Here, we started with a_n = n^2. And even if the differences do not end up vanishing, as long as they stay small this can be used for computation. This is what Babbage and Lovelace were doing with their Difference Engine in the 19th century, and what early computers (human and mechanical) spent most of their time doing.
For now on, I'll write sequences like functions; just remember that the domain is the nonnegative integers.
Let f(x) be a sequence. Then, ∆f(x) = f(x+1) - f(x). ∆ is the difference operator, analogous to the derivative operator. Similarly, there's a summation operator, similar to integration:
∑f(0) = 0,
∑f(1) = f(0),
∑f(2) = f(0) + f(1), etc.
Note that
∆(f + g) = ∆f + ∆g,
∆c = 0 (c constant),
∑(f + g) = ∑f + ∑g.
Exercise:
a) Verify that ∆∑f(x)= f(x) for all x.
b) Verify that ∑∆f(x)= f(x) - f(0) for all x.
Now, take the original problem:
f(x+1) = 3f(x) - 2.
f(x+1) - f(x) = 2f(x) - 2
∆f - 2f = -2
This looks like the differential equation
(*) f' - 2f = -2
That's an easy one to solve: the homogenous version
f' - 2f = 0 has solutions f(x) = c e^{2x}.
But, HS students won't understand that, so just ask what the solutions of
∆f - 2f = 0, or even
∆f - cf = 0 are.
Then, find a simple solution of the original equation (*). Best is to let f be a constant function.
Then, try to see what ∆ does to monomials, polynomials, and try to mimic the well-known formulas of differential calculus, even if the students don't know those.
Post a Comment