in summation...

In an earlier post, I wondered out how to get a closed form for my car debt. The program I wrote can be actually thought of as a recurrence relation:

   debt at the very beginning = initial debt at zero months

   debt(n) = monthly interest * (debt from last month - my monthly car payment)
             and where n has to be greater than 0.

But since that's a bit wordy, I'll use some shorter variable names when I'm talking about the debt I'm incurring at month n:

   d(n) = I * (d(n-1) - P)     for n > 0
        = I * d(n-1) - I*P     for n > 0

I didn't quite remember how to get a closed form for this formula at the time. Yesterday, though, as I was quaffing a coffee at Cape Cod, I flipped through Concrete Mathematics. There in the first few pages of the book was the technique I needed!

The core idea is to use a summation factor to make the function I'm solving for a little simpler. For the recurrence above,

   (1/I)^n

is a good summation factor. When I multiply my recurrence with it, I get:

   d(n)/(I^n) = d(n-1)/(I^(n-1)) - P/(I^(n-1))     for n > 0

The reason this is simpler is because I can consider a parallel formula:

   S(n) = d(n) / (I^n)

which I can use to restate the recurrence as:

   S(0) = d(0) / (I^0) = d(0)         (since anything to the zeroth power is 1)
   S(n) = S(n-1) - P/(I^(n-1))        for n > 0

And now S(n) is, structurally, simple enough to be treated as a straight summation rather than a wacky recurrence:

   S(n) = d(0) - sum across k from 1 to n of: P/(I^(k-1))

        = d(0) - P * sum across k from 0 to (n-1) of: (1/I)^k

        = d(0) - that horrendous sum

But it turns out that that horrendous sum is actually not bad at all. If we squint our eyes at it, it's a geometric sum, and those have a very nice closed form: it's the "first term - the first excluded term in the sum, divided by one minus the term ratio". That is, if I'm doing:

   a^0 + a^1 + a^2 + ... + a^n

I don't have to actually add up all those terms: I can just do:

   ((a^0) - a^(n+1)) / (1 - a)

So by applying the transformation on that geometric sum, I can get a closed form for S(n):

   S(n) = d(0) - P * sum across k from 0 to (n-1) of: (1/I)^k
        = d(0) - P*(1 - (1/I)^n)/(1 - 1/I)

But S(n) isn't what I was originally going after: I was going after d(n), so let me backpatch that fix in:

   S(n) = d(n) / (I^n), so
   d(n) = S(n) * I^n

That is, my car debt at any given month is going to be:

   d(n) = I^n * (d(0) - P*(1 - (1/I)^n)/(1 - 1/I))

Whew! Let's try that out:

(module car-payment-2 mzscheme
 ;; debt: number number number number -> number
 ;; Returns the amount of money owed after months pass,
 ;; given a particular monthly payment and apr rate.
 (define (debt months initial-debt monthly-payment apr)
  
   ;; closed-form: number number number number -> number
   ;; This is a closed form solution for the recurrence:
   ;;
   ;; d(n) = I * (d(n-1) - P)
   ;;
   ;; d(n) = I^n * (d(0) - P*(1 - (1/I)^n)/(1 - 1/I))
   (define (closed-solution n d0 P I)
     (let* ([I^n (expt I n)]
            [1/I (/ 1 I)]
            [1/I^n (/ 1 I^n)])
       (I^n . * .
            (d0 . - .
                ((P . * . (1 . - . 1/I^n))
                 . / .
                 (1 . - . 1/I))))))
  
   (let ([monthly-interest (+ 1 (/ apr 12))])
     (closed-solution months
                      initial-debt
                      monthly-payment
                      monthly-interest))))

and let's look at a few values:

> (debt 0 16300 327.93 0.0767)
16300
> (debt 1 16300 327.93 0.0767)
16074.158147416665
> (debt 2 16300 327.93 0.0767)
15846.872788992236
> (map (lambda (x) (debt x 16300 327.93 0.0767))
      (list 0 1 2 3 4 5 6 7 8 9 10))
(16300
16074.158147416665
15846.872788992236
15618.13469831854
15387.934590015295
15156.263119353142
14923.110881874338
14688.46841301098
14452.32618770081
14214.67462000053
13975.5040626967)
> (map (lambda (x) (debt x 16300 327.93 0.0767))
      (list 56 57 58 59 60))
(1150.9196104211048
828.2498856810436
503.5177636170277
176.71006207281036
-152.1864853637734)

I did a little fist-pump after I got this working. CS students are weird.