## Wednesday, June 20, 2007

### Take any number, Add Three, Divide the Result by -1. Now Repeat this! Recursive Sequences and Functions Part I: Grades 7-12

Here is the link to the Carnival of Math Edition X.

The following is the first in a series of investigations in recursive sequences and functions for middle school and secondary students. This apparently advanced topic is accessible to prealgebra students at an introductory level. The first few parts of the investigation below are appropriate for the younger students. The remaining parts require more algebraic facility and reasoning. The problem in the title of this post doesn't begin until more than halfway down the page (after some background is developed). Do not skip the background below since it's referred to frequently in the activity. My personal experience is that this topic is highly engaging to students. Considering the connection between recursion and fractals, this topic is certainly part of most standards-based curricula. The terminology of recursion (recursively-defined sequences, recursive description, recursive function, recurrence relations, etc.) is quite confusing at first. Many confuse these ideas with iteration, a general term for describing repetitive algorithms.
Finally, from a pedagogical point of view, please note how the Rule of Four is implemented in the activity below: We start with a verbal description of the rule of formation of a sequence (in natural language), followed by a concrete numerical representation of the terms, followed by symbolic representation. One could also depict the terms graphically on a number line or in the coordinate plane if the function model is used for the sequence.
----------------------------------------------------------
I should probably save this for the new school year but it's hard for me to suppress ideas when they begin to crystallize. I've been thinking for some time about how we can introduce recursive functions in prealgebra through advanced algebra and beyond. I enjoy taking sophisticated ideas and reducing them to basic principles, then developing lessons that explore the topic in some depth. Moreover, this particular topic reveals the interconnectedness of mathematics in a particularly elegant and beautiful way.

Background (Needed for the Investigation Below!)
Consider the sequence 1,2,4,8,...
Elementary students can generally guess the most likely value for the next term, 16. They also are expected to identify the 'rule' of forming the 'next' term, namely doubling or multiplying by 2. This is an important stage in their development of algebraic reasoning - abstraction or generalization. In addition, they should begin to recognize that the terms of the sequence can be described generally as powers of 2, even though a formal introduction to exponents normally begins in 7th grade.
Middle school students should progress to the function table format of a sequence:
n.....an
1.....1
2....2
3....4
4....8
5....16
...

Elementary and middle school students should be able to verbalize in natural language that 'you double the terms'. As educators, we need to lead them to a more formal relationship by a line of Socratic questioning like: "Double what? To get what?" Students should then be able to express the idea that each term is twice the previous term. We can ask, "Which term doesn't follow that rule?"
To symbolically describe this sequence, we can write:
a1 = 1
an+1 = 2 ⋅ an, n = 1,2,3,...
This is known as a recursive description of the sequence. Try it - replace n by 1,2, and 3 and see if it produces the terms above.
[Note: Later on, in more advanced algebra, students should be able to express this as a recursive function: f(1) = 1; f(n+1) = 2f(n), n = 1,2,3,...]

The closed or general form requires a knowledge of exponents but is accessible to 7th graders
an = 2n-1, n = 1,2,3,... Try it!
(If you're questioning my sanity (you wouldn't be the first!) about introducing such sophisticated mathematics to general 7th graders, well, I do have a legitimate basis for this curricular decision - more later...).

Powers lend themselves naturally to a recursive description and this is why I begin with the above example. Recursive thinking develops when we ask questions like:
If we know what 25 is, how would we obtain 26?
To deepen this understanding further:
If we know what 298 is, how would we obtain 2100?
Does the exponent key on a calculator help students see these relationships? Not really! The calculator is useful to demonstrate powers and exponents but not for this discussion. Later on, the graphing calculator can be used to enter recursively-defined functions (after they've learned the ideas!).

If you're very familiar with recursively defined sequences and functions, you've probably left this page already! However, the idea of an operation or function being defined in terms of itself is a beautiful and very important notion in mathematics. This type of thinking was necessary for Mandelbrot to develop the notion of fractals, which defines a process in which each stage is defined in terms of the preceding stage or stages - that is recursive thinking!

Ok, by now you're wondering what happened to the title of this blog!
THE PROBLEM:
TAKE ANY NUMBER, ADD THREE, DIVIDE (OR MULTIPLY) THE RESULT BY -1. NOW REPEAT THIS SEQUENCE OF OPERATIONS ON THE RESULT YOU OBTAINED.

Student Activity:
1. Start with the number 6 and follow the instructions above. Repeat this 2 more times. List the first 4 terms of the sequence obtained. Write a brief description of what you observe about this sequence.
2. This time start with a different integer. Again, list the first 4 terms of the sequence obtained and your observations.
3. By now you've concluded that the sequence obtained will alternate in the form a,b,a,b,...
Which one of the original operations (add 3, multiply result by -1, etc.) do you believe is causing the sequence to repeat like this?

The remaining parts require algebra background.

4. If the first term is x, verify algebraically that the sequence will alternate.
5. You've now determined that the sequence appears to be repeating but not constant like a,a,a,a,... For what value of x, the first term, will the sequence be constant, i.e., all terms will have the same value?
6. Write a recursive definition (refer to how we did this for powers) for our sequence whose first term is x. We'll start you off:
a1 = ____
an = __________, n = _______
7. BACKGROUND
The algebraic formulation of the recursive description in #6 was fairly straightforward, since it is just a symbolic representation of the verbal "Take any number, add three, then divide the result by -1." As useful as this may be, we often a need a general formula for the nth term as a function of n, rather than in terms of preceding terms of the sequence. That last sentence was fairly complex, so here's an illustration:
Let's assume the first term is 6. Then the nth term can be described as:
an = 6 if n = 1,3,5,7,... (i.e., n is odd)
an = -9 if n = 2,4,6,... (i.e., n is even).
This would allow us to find any particular term, say the 100th term, without knowing the values of preceding terms. Such a description is known as a general description or the closed form of the sequence. Such a formula is often very hard to determine, whereas the recursive form is easier to formulate. In our problem, the general formula for the nth term had to be given in two cases or piecewise as mathematicians term it.
It is possible to give a single formula for all of the terms of our sequence as a function of n:
an = -7.5(-1)n - 1.5, n = 1,2,3,...
Verify this formula
for our sequence above: 6,-9,6,-9,6,-9,...
8. Change the original problem to:
Take any number, add 2 to it and multiply the result by -1. Repeat.
(a) Starting with an original value of 6 (as the first term), list the first 5 terms of the sequence.
(b) Write a recursive description for this sequence.
(c) Write a piecewise formula for the nth term as in the background example above.
(d) Write a single formula (closed form) for the nth term in terms of n for this sequence.

9. (More Challenging)
A sequence is defined verbally by:
Take any number, add k to it and multiply the result by -1.
(a) If the first term is x, write a recursive description for this sequence.
(b) Write a piecewise formula for the nth term.
(c) (Super Challenge) Write a single formula (closed form) for the nth term in terms of n for this sequence.

Eric Jablow said...

Here's some other activities for your students (or your successor's students).

1) Prove that the n-disk Tower of Hanoi problem can be solved in 2^{n} − 1 steps.

You can start by showing that (call the number of steps required to solve the n-disk problem h_n),

h_{n+1} = h_n + 1 + h_n.

2) Explain the Collatz problem, which is unsolved:

Start with any positive integer n, and define the sequence {a_k} as:

a_0 = n

a_{k+1} = a_k / 2 if a_k is even,

a_{k+1} = 3a_k + 1 if a_k is odd.

Does this sequence always end up with the '1-cycle', 1,4,2,1,…? Is there a starting point n such that the sequence forms another cycle, or is there a starting point n such that the sequence never repeats but remains bounded from below.

We believe that every n eventually leads to the 1,4,2,1 cycle. No one has proven it yet. Every n < 2.88×10^{18} leads to the 1-cycle. But it can take a long time for any given number. Wikipedia notes that 27 leads to 1 after 111 steps.

Dave Marain said...

Eric--
Yes, Towers of Hanoi is a wonderful problem to get the students hooked on a recursive procedure. BTWm will the Clay Institute award \$1 million if a student solves the Collatz Problem!
Actually giving some students an 'unsolved' problem would really pique their interest. I know I want to try it. The fact that such an innocent recursive definition as this one can lead to uncertainty is fascinating. That's why I like this topic.
The repetition in the problem in my post is easy to grasp. If we change the relationship to
a_[n+1] = C(a_n) + D, we obtain a more general linear recurrence relation. If C is not equal to -1, the sequence is more complicated of course. Part II of this investigation is leading in this direction and will develop a general solution (closed) to this inhomogeneous case. It will take me some time to develop a logical sequence of questions that students can manage. I'm not sure some readers appreciate how labor intensive it is to write these activities. It's considerably harder than writing an exposition of the method.
Anyway, what I'm actually leading up to is the closed solution of the most famous recursively defined sequence: 1,1,2,3,5,8,...
Getting students to this will be a challenge for me. The easy way of course is to give them the formula and have them check it but...

I feel like very few will appreciate this series of activities, particularly in the hot summer months. Do you think it will be worth the effort?

jonathan said...

I had a very smart, very lazy student in combinatorics this past fall. You've seen my "Ghost the Bunny" problem?? The bunny hops up one or two steps at a time, how many ways can he reach the top of a flight of 12 steps.

The lazy student stared and stared and stared at the problem (while his groupmates scribbled vigorously). And after, I don't know, 15? minutes, called me over to offer the sum of some combinations (IOW, he found the closed form for n=12 without noticing the recursiveness)

Strange kid. Very smart.

I should add that, at that level, the problem is far less enaging, as the kids already have ALL the tools to analyze and find the closed form. There is no "stretch," just application - all of your worksheets are designed to provide stretch.

mathmom said...

Thanks, Dave, I've bookmarked this to use with my middle school group next year.

Dave Marain said...

jonathan and mathmom--
thanks for the generous comments... Let me know if students find this problem reasonable next term.
Of course by then this problem will be hidden in the archives and most will not even see it. How do I keep some of these posts active long after other posts have moved them off the screen? I have a few ideas (like setting up links on the sidebar to some of my favorites) or creating a post consisting of links, but I would like other ideas. Blogger may not be the right medium for this or I am simply clueless, which is far more likely!
Take a look at the Geometry Challenge I just posted. Either it's a good problem or I messed up and it's really simple! I'm thinking of sending it to the next Carnival along with this post. I'd love your opinions!

jonathan said...

Dave,

can you create (and update) an index? Then you would just need a link to that index (really, a post of links to worksheets).

This might be something like the contract tabs I have at the top of my page.

Your other ideas might work as well.

David said...

I like to use Excel when teaching about recurrences. Generating recursive sequences in Excel is quick and easy, and I think it helps to make the concept more intuitive and visual. Also, students realize that being able to use Excel is a useful job skill, and this helps to hold their interest.

While preparing a lesson on the logistic map, I found that I could generate a reasonable picture of the bifurcation diagram in Excel, but I left this out because I was short on time.