Prev: Word problems for grammars
Next: How many edges are there in semi cubic digraph
From: jackbenimble999 on 4 Jul 2008 11:42
I'm a complete newbie to computation theory, so unfortunately my
question(s) are likely to seem really naive.

This has to do with an example from Sipser's Theory of computation,
2nd Edition, page 24 to 25.

It's an inductive proof of loan calculation.

He's proving this.


P sub t = PM^t - Y(M^t -1/M -1)

Where

P is the remaining Principal
Y is the monthly payment
M = 1 + I (capital i) /12 where I is the yearly interest rate.

So, if you compound monthly, then the interest rate would be I / 12.
And to get the new principal you get the remaining principal. eg. Pk+1
= Pk * (1 + I /12). But before you do that, you have to subtract the
Y, because the bank apparently compounds BEFORE subtracting the
payment, P sub k + 1 = P sub k+1 = (P sub k * M) - Y

That part that make sense to me. But the theorem

for each t >= 0:

P sub t = PM^t - Y ( (M^t -1) / (M - 1) )

Where does this come from? Why are we all of a sudden bring powers
into this whole thing?



So, in the case that t = 0, we have to prove this theorem is true.

So, basically, he says that M^-0 = 1, which means that the whole Y
( (M^t -1) / (M - 1) ) becomes 0. (because Y * (0 / M) = 0).

so, that leaves you with P sub t = PM^t. Again, since P^0 = 1, we're
left with P sub t = P * 1, which means the P = P. So, the base case is
true.

But, now, here's the tricky part.

I still haven't figured out why on earh all of a sudden we have these
exponents.

Ok, so, the only way I can really get a grip on this is to plug in
some numbers.

Let's say that the amount of the loan is $1000, at 12%, and say you
pay $100 per month.

So, P = $1000.
M = 1 + (12%/12) = 1 + 1% = 1.01.


The first month, (t = 0), we already know P = P = $1000.

Now for t =1. Let's plug it in to this crazy equation:

P sub t = PM^t - Y(M^t -1/M -1)

1. replace t with 1

P sub 1 = P sub 0 * M^1 - Y(M^1 -1/M -1)

2. replace the M with 1.01

P sub 1 = P sub 0 * 1.01^1 - Y( (1.01^1 -1) / (1.01 -1) )

3. Anything to the first is itself, so the above becomes

P sub 1 = P sub 0 * 1.01 - Y( (1.01 -1) / (1.01 -1) )

4. Do some more math

P sub 1 = P sub 0 * 1.01 - Y( 1 )

5. Do some more math

P sub 1 = P sub 0 * 1.01 - Y( 1 )

5. Substitute in P an Y

P sub 1 = 1000 * 1.01 - 100 ( 1 )

6. More math

P sub 1 = 1010 - 100

6. Answer

P sub 1 = 910.

Check against an internet calculator:

Wow...it's right.

http://www.finaid.org/calculators/scripts/loanpayments.cgi

Last column is remaining balance

1 $100.00 $10.00 $90.00 $10.00 $90.00 $910.00
2 $100.00 $9.10 $90.90 $19.10 $180.90 $819.10
3 $100.00 $8.19 $91.81 $27.29 $272.71 $727.29
4 $100.00 $7.27 $92.73 $34.56 $365.44 $634.56
5 $100.00 $6.35 $93.65 $40.91 $459.09 $540.91
6 $100.00 $5.41 $94.59 $46.32 $553.68 $446.32
7 $100.00 $4.46 $95.54 $50.78 $649.22 $350.78
8 $100.00 $3.51 $96.49 $54.29 $745.71 $254.29
9 $100.00 $2.54 $97.46 $56.83 $843.17 $156.83
10 $100.00 $1.57 $98.43 $58.40 $941.60 $58.40
11 $58.98 $0.58 $58.40 $58.98 $1,000.00 $0.00




The third month should be 819.10, according to the above chart.


Let's plug the numbers:


P sub t = PM^t - Y ( (M^t -1) / (M - 1) )

The 3rd month, (t = 2)

Now for t = 2. Let's plug it in to this crazy equation:

P sub t = PM^t - Y(M^t -1/M -1)

1. replace t with 2

P sub 2 = P sub 1 * M^2 - Y(M^2 -1/M -1)

2. replace the M with 1.01

P sub 2 = P sub 1 * 1.01^2 - Y( (1.01^2 -1) / (1.01 -1) )

3. Calculate the exponent math

P sub 2 = P sub 1 * 1.0201 - Y( (1.0201 - 1) / (1.01 -1) )

4. Do some more math

P sub 2 = P sub 1 * 1.0201 - Y( .0201 / .01 )

4a. keep going

P sub 2 = P sub 1 * 1.0201 - Y( 2.01 )

5. Substitute in P and Y

P sub 2 = 910 * 1.0201 - 100( 2.01 )

6. More math

P sub 2 = 910 * 1.0201 - 100( 2.01 )

7, More math

P sub 2 = 928.291 - 201

8, Answer

P sub 2 = 727

Wrong - 727 - but it'a actually the remaining principal for the
following month...????

2 $100.00 $9.10 $90.90 $19.10 $180.90 $819.10 <=== wanted
3 $100.00 $8.19 $91.81 $27.29 $272.71 $727.29 <=== got

Ouch. 'm sure I made some kind of an error, but i went from t = 0 to
1 to 2. 0 and 1 checked out, but two came out wrong. Where's the
mistake?

Jack



From: cplxphil on 5 Jul 2008 21:04

Hello,

I've asked several questions on here, so I figure I should try to
answer one.

To begin with, good choice on selecting Sipser's textbook; I'm working
through it myself, and it's fantastic. If you aren't familiar with
induction, however, you might want to try another textbook first to
familiarize yourself with some of the basics of mathematics and
proof. He doesn't spend a lot of time on the basics, so you might
find yourself completely lost when he delves into the proofs later in
the book. (I'm a fourth-year undergraduate math major, and I struggle
with some of his proofs later in the book.)

Also, just as a heads up, induction isn't really "complexity
theory"...you'll get to that in a few chapters. Induction is a basic
mathematical technique used to prove all sorts of things in various
different branches of mathematics. It's particularly prevalent in
discrete mathematics.

> I still haven't figured out why on earh all of a sudden we have these
> exponents.

The derivations of some of these formulas are fairly non-trivial, at
least to a beginning student. He isn't going to tell you why the
formula works or how he came up with it; he's just going to prove it.
I am not entirely familiar with the problem, but exponents do appear
somewhat frequently when you try to derive non-recursive formulas from
recursive equations.

> Let's say that the amount of the loan is $1000, at 12%, and say you
> pay $100 per month.

Ok.

> The third month should be 819.10, according to the above chart.

1000*(1.12)^2-100*((1.12^2-1)/(1.12-1))
= 1254.4 - 212
= 1042.4

Ok, I don't know what your chart says, but t = 2 should give you
1042.4 according to the equation.

The recursive formula is: P(k+1) = P(k)*M - Y.

You said P(0) = 1000.

Then by this formula, P(1) = P(0)*1.12 - 100
Thus, P(1) = 1120 - 100 = 1020

Then P(2) = P(1)*1.12 - 100
So P(2) = 1020*1.12 - 100 = 1042.4

The equations check out. I have no idea what your charts told you,
and honestly your transcript of your work was too lengthy to follow.
I would recommend sticking strictly to the formulas in the textbook,
and not consulting some internet calculator that may be calculating
something different. There's no error here.

If you're really interested in where the exponents come from, I can
try to re-derive the non-recursive equation for you based on the
recursive one. Let me know if you'd like me to do that.

-Phil
 | 
Pages: 1
Prev: Word problems for grammars
Next: How many edges are there in semi cubic digraph