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.