Does solving a recurrence relation by iteration have two different meanings?

Question

I've seen iteration used by plugging numbers in and not simplifying and guessing the explicit formula, e.g., $t_n$ plug $n=1,2,3,4$ in and guess the explicit formula. The other way I've seen is plugging the variables in e.g. plug $t_{n+1}$ in for $t_n$ and try to see the explicit formula that way. Am I right that both these methods are known as iteration? How do you decide which one to use?

For example this is from a textbook:

Let $a_k=a_{k-1}+2$ and $a_0=1$ Use iteration to guess an explicit formula for the sequence. $a_1=a_0+2=1+2$
$a_2=a_1+2=1+2+2$
$a_3=a_2+2=1+2+2+2$
$a_4=a_3+2=1+2+2+2+2$
It appears helpful to use shorthand $a_1=a_0+2=1+2$
$a_2=a_1+2=1+2 \cdot 2$
$a_3=a_2+2=1+3 \cdot 2$
$a_4=a_3+2=1+ 4 \cdot 2$

Guess: $a_n=1+n \cdot 2 = 1+2n$

vs this one

Here is an example of solving the above recurrence relation for g(n) using the iteration method:

  g(n) = g(n-1) + 2n - 1
       = [g(n-2) + 2(n-1) - 1] + 2n - 1 
                 // because g(n-1) = g(n-2) + 2(n-1) -1 //
       = g(n-2) + 2(n-1) + 2n - 2 
       = [g(n-3) + 2(n-2) -1] + 2(n-1) + 2n - 2 
                 // because g(n-2) = g(n-3) + 2(n-2) -1 //
       = g(n-3) + 2(n-2) + 2(n-1) + 2n - 3 
         ...
       = g(n-i) + 2(n-i+1) +...+ 2n - i 
         ...
       = g(n-n) + 2(n-n+1) +...+ 2n - n 
       = 0 + 2 + 4 +...+ 2n - n
                 // because g(0) = 0 //
       = 2 + 4 +...+ 2n - n
       = 2*n*(n+1)/2 - n
                 // using arithmetic progression formula 1+...+n = n(n+1)/2 //
       = n^2

Clearly these methods are different so are they both called iteration and when do you know which to use? I guess the first one is simpler since it has fewer variables.

Answer 1

I usually refer to the second method as unwinding or unwrapping the recurrence, but method of iteration is not an unreasonable name for it, and I have seen it used in a number of places. The first method isn’t described clearly enough for me to be certain of what’s intended. It’s often possible to calculate a few terms of a recursively defined sequence and spot a pattern, which one can then try to prove is real, usually by induction. If that’s what the author has in mind, I wouldn’t even call it a method. However, the way the computations are written out suggests that the author is actually thinking of something very much like the second method, but done less formally.

I almost always begin by calculating some values, partly to get a feel for the sequence and partly in hopes of spotting a pattern. Even if I don’t spot a pattern, I can plug my values into the On-Line Encyclopedia of Integer Sequences to see whether they’re part of some known sequence.

The unwinding method is helpful only if you’re dealing with a first-order recurrence, and the same is usually true of simple pattern-spotting. If the first-order recurrence is fairly simple I might use the unwinding technique, and I’ve often taught it, because it requires no advanced tools, but there are other methods that are often more efficient.