One way to specify a sequence of numbers is recursively; that is, the first one or more terms in the sequence are stated, and then a formula for the general term of the sequence is given in terms of one or more previous terms. For example, in the famous Fibonacci sequence, the first two terms are both 1, and each subsequent term is the sum of the two previous terms. In symbols,
$a_1 = 1, \, a_2 = 1, \; \textrm{and for each} \; n \ge 3, \; a_n = a_{n – 1} + a_{n – 2}$
The relation in the previous equation is called a recurrence relation, and often also called a difference equation. Using the recurrence relation, the first few terms of the Fibonacci sequence can be generated: $1, 1, 2, 3, 5, 8, 13, 21, 34, … $.
Recurrence relations arise in some combinatorics problems, where the thinking process used to model a situation mathematically naturally leads to a relation among the terms of a sequence. The also arise in the solution process of some differential equations, particularly those solved using power series. Recurrence relations are convenient for some purposes; for example, as we already mentioned in the process of thinking through a combinatorics problem, or in constructing algorithms suitable for processing by computers. Recurrence relations emphasize how the terms are related to each other; in the Fibonacci sequence, each term (after the first two) is the sum of the two previous ones. However, in other circumstances it is preferable to obtain a formula for the general term of a sequence as a function of the term number n that does not involve any other terms of the sequence. For instance, if you wish to know the 417th term of the Fibonacci sequence, or if you wish to study the asymptotic behaviour of the sequence, then a formula for the nth term is handy. Obtaining such a formula is what is meant by “solving the recurrence relation.”
I am currently creating some notes on combinatorics, and last night I was writing up an example of solving a linear second-order recurrence relation. When deriving equations or doing calculations, I do as much as possible mentally, only using scratch paper to draft material by hand when absolutely necessary. Every page or two I take a break from composing to typeset the work (I use LaTeX), and then I read the pdf file to check for errors and correct them.
The recurrence relation I was solving last night is
$a_0 = -1, \, a_1= 2, \; \textrm{and for each} \; n \ge 2, \; a_{n + 2} = a_{n + 1} + 2a_n + n$
In solving this recurrence relation last night, I used scratch paper minimally, just jotting down a few key steps, and doing most of the calculations mentally. My result:
$a_n = \dfrac{1}{12} \left \{ 2^{n + 3} – 17(-1)^n – 6n – 3 \right \}$
(To learn more about solving such recurrence relations, you might try here.)
OK, now it was time to check the formula. To do this, I first used the original recurrence relation to generate the first few terms of the sequence, which I organized in a table:
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| an | -1 | 2 | 2 | 9 | 17 | 40 | 80 |
Then I used the formula I worked out to calculate the terms of the sequence. Unfortunately, they didn’t match, so I had made an error. So I carefully repeated the derivation of the formula, this time in more detail on my scratch paper. I carefully compared my new work to the typeset material that I had previously produced. They were identical.
This was annoying. I had used the same writing and checking procedure for quite a few other recurrence relations previously, and all had worked well. Perhaps I was just tired … it was past my bedtime, so I decided to leave it and sort it out in the morning.
This morning I reviewed the derivation, and the construction of the table of values, and found no error. Now I was quite annoyed. Forgetting that I had used this method quite successfully on almost a dozen similar examples the previous day, I began to berate myself for relying so much on mental calculations. “Haste makes waste,” I said to myself. “If you had done the problem in detail, on paper, the first time, you wouldn’t have made a mistake that you are now wasting a lot of time unsuccessfully trying to correct!” Or words to that effect!
Perhaps you’ve already figured out where I went wrong, but if not then you might enjoy finding my error before I continue the story.
* * *
I bounced back and forth between checking the derivation and checking the table of values, and eventually I figured out where I had gone wrong. The table of values is incorrect. Here’s an example of my error: To calculate $la_4$, I added $a_3$ and twice $a_2$, and finally added 4, because $n = 4$. And this is the error: If we carefully write out the instance of the recursion relation that is needed to calculate $a_4$, we see that we must substitute 2 for n, NOT 4:
$a_{n + 2} = a_{n + 1} + 2a_n + n$
$a_{2 + 2} = a_{2 + 1} + 2a_2 + 2$
$a_4 = a_3 + 2a_2 + 2$
Here is the corrected table:
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| an | -1 | 2 | 0 | 5 | 7 | 20 | 38 |
How did I miss this, when I had done it correctly perhaps ten times in ten previous examples? (Each time, I was very careful to use the appropriate values of n to determine the terms in the table.) It would be easy to rationalize this in any number of ways (I was tired, I was working on several projects at once, I was interrupted by the telephone just before making the error, …). And of course, one can always rely on the well-worn self-abuse (I am so stupid, I am such an idiot, …). But rationalization and self-abuse are not useful; it would be far better to come up with some good thinking habits that might minimize the time needed to catch future errors, or prevent them entirely. For we will always be tired, always be working on several projects at once, always be interrupted, … .
I am particularly struck by the fact that I had done such calculations correctly quite a number of times before I somehow forgot how to do them correctly and made an elementary error. So what could I do next time to prevent such an error? How about this:
- Haste makes waste.
- I could have checked several entries in the table instead of just one. Had I done so I might have detected a pattern that would have directed my attention to the error a lot sooner. (Admittedly this may not be easy in this case, but I think it’s a good habit in general.)
- I could have written out a sample calculation for an entry in the table in full detail, instead of relying so much on mental calculations. (This is how I eventually clued in to the error, but I could have done so much earlier.)
- Most importantly, I should have constructed the formula so that the value of n in the table matched the value of n in the formula.
The last item on the list is key, and I’m still a little bewildered about why I forgot this point when I was aware of it in previous calculations. But I think this bewilderment is the deeper point here: We are bound to make such mistakes sometimes, because our mental capacities vary in time, and if the cognitive load in a certain problem exceeds our current capacity, then the probability of error increases. By choosing good notation we can reduce the cognitive load, and thereby minimize errors.
One can make the meaning of n consistent in the table of values and in the formula by (for example) replacing each instance of n by (n – 2) in the formula:
$a_{n + 2} = a_{n + 1} + 2a_n + n$
$a_{(n – 2) + 2} = a_{(n – 2) + 1} + 2a_{n – 2} + (n – 2)$
$a_n = a_{n – 1} + 2a_{n – 2} + n – 2$
The latest recurrence relation corresponds with the correct table, with a consistent interpretation for n: for example, to determine the 5th entry in the table, just replace n by 5 in the formula.
* * *
There is a further lesson here for me, both as a writer and a teacher. We must be careful to select notation carefully in a way that will minimize the errors that our students and readers might make. Let us lead them not into temptation. (This means I will have to spend time going over the notes I have just created and make changes in the formulas; but so be it.)
Having said that, I recognize that errors are essential in learning mathematics, and we should do everything we can to facilitate our students in making errors usefully and learning to correct them gracefully. For example, if the core of student practice is to solve problems, then students should not blitz from one problem to the next. There is so much time pressure on students nowadays that many students habitually solve a problem, check the answer in the back of the book, and then immediately move on to the next problem. We should encourage students to linger on problems once they have been solved, and to compare and contrast them with related problems. Above all we should model this for students so they learn what to do.
Additionally, my error confirms a feeling I have had for a long time. Getting one’s hands dirty with the details of calculations and derivations is an essential element to deep understanding. That is, an over-reliance on electronic assistance (calculators, graphics calculators, software) too early in the learning process is not effective. Once a student has understood enough by getting his or her hands dirty, then using electronic automation is a marvelous way to explore further. So I am not arguing that we should not use technology in education, only that we should postpone its use until students have had a chance to play with their own hands enough to get a reasonable understanding. I heartily approve of using technology, just not too soon. (On this point, I know some teachers will disagree with me, as some teachers use technology to introduce, develop, and explore mathematical concepts, some to the exclusion of pencil-and-paper work.)
So, although the error was annoying, it was very instructive, at least for me!
(This post first appeared at my other (now deleted) blog, and was transferred to this blog on 21 January 2021.)