0

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.

Celeritas
  • 2,743

1 Answers1

2

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.

Brian M. Scott
  • 616,228
  • I replaced the first example with another one that appears to use the same technique but is better illustrated. Could you give it a look again and let me know if is iteration and when I should use it as opposed to the second? – Celeritas Nov 29 '13 at 03:29
  • 2
    @Celeritas: I don’t see it as being different from the earlier example in any essential way. It’s still just basic pattern recognition or just possibly a very informal version of the unwinding technique. It doesn’t change anything that I said in my answer. – Brian M. Scott Nov 29 '13 at 03:33
  • Ok I wanted to double check since you said you didn't understand the first example. – Celeritas Nov 29 '13 at 03:38
  • You say the second technique is called "unwinding" so does that mean iteration is something entirely different? – Celeritas Nov 29 '13 at 03:39
  • 1
    @Celeritas: I usually refer to the technique of the second example as unwinding or unwrapping the recurrence, and I’ve seen others use the terms. I’ve also seen it called the method of iteration. I don’t think that any of these names could really be said to be the standard name, and I don’t think that method iteration is used widely enough to be considered standard for any method. – Brian M. Scott Nov 29 '13 at 03:43