Jesse's Blog
SICP-Exercise-1.13
Jesse 发表于 2008-08-23 09:42:48
Exercise 1.13.
Using mathematical induction, it's not hard to prove:
Fib(n) = (phi^n - psi^n)/sqrt5
0). The base cases are easy:
Fib(0) = 0 = (phi^0 - psi^0) / sqrt5
Fib(1) = 1 = (phi^1 - psi^1) / sqrt5
1).. The induction step:
Assume for ALL k <= n, we have:
Fib(k)=(phi^k - psi^k)/sqrt5
So,
Fib(n+1)
= Fib(n) + Fib(n-1)
= (phi^n - psi^n)/sqrt5
+ (phi^(n-1) - psi^(n-1))/sqrt5
= phi^(n-1) * (phi+1)
- psi^(n-1) * (psi + 1)
= phi^(n-1) * phi^2
- psi^(n-1) * psi^2
(because phi+1=phi^2, and the same to psi)
= (phi^(n+1) - psi^(n+1))/sqrt5
====
Then having such a lemma, we have:
Fib(n) = (phi^n)/sqrt5 - something,
where the something = (psi^n)/sqrt5, but we know abs(psi) is smaller than 1,
which will become arbitrarily small when raised to n times (if n is big
enough). So Fib(n) is the closest integer to (phi^n)/sqrt5.(The logic seems not that good)
Using mathematical induction, it's not hard to prove:
Fib(n) = (phi^n - psi^n)/sqrt5
0). The base cases are easy:
Fib(0) = 0 = (phi^0 - psi^0) / sqrt5
Fib(1) = 1 = (phi^1 - psi^1) / sqrt5
1).. The induction step:
Assume for ALL k <= n, we have:
Fib(k)=(phi^k - psi^k)/sqrt5
So,
Fib(n+1)
= Fib(n) + Fib(n-1)
= (phi^n - psi^n)/sqrt5
+ (phi^(n-1) - psi^(n-1))/sqrt5
= phi^(n-1) * (phi+1)
- psi^(n-1) * (psi + 1)
= phi^(n-1) * phi^2
- psi^(n-1) * psi^2
(because phi+1=phi^2, and the same to psi)
= (phi^(n+1) - psi^(n+1))/sqrt5
====
Then having such a lemma, we have:
Fib(n) = (phi^n)/sqrt5 - something,
where the something = (psi^n)/sqrt5, but we know abs(psi) is smaller than 1,
which will become arbitrarily small when raised to n times (if n is big
enough). So Fib(n) is the closest integer to (phi^n)/sqrt5.(The logic seems not that good)
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾