Monday, October 16, 2006

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.

No comments: