|
| Homework 16Details
- (10)
Recall that the Fibonacci sequence is given by \(f_0=0\), \(f_1=1\), and for
\(n>1\), \(f_n=f_{n-1}+f_{n-2}\).
Use substitution (induction) to prove that for all \(n\geq 0\), the closed form is given by
\[f_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \sqrt{5}\left(\frac{1-\sqrt{5}}{2}\right)^n.\]
The following identities will help you in the algebraic steps:
\[\left(\frac{1+\sqrt{5}}{2}\right)^2=\left(\frac{1+\sqrt{5}}{2}\right)+1 \mbox{ and } \left(\frac{1-\sqrt{5}}{2}\right)^2=\left(\frac{1-\sqrt{5}}{2}\right)+1 \]
-
(10) Use iteration to find a closed formula for \(T(n)=T(n-1)+n^2\), \(T(1)=1\).
Show all of your work and simplify your answer.
|
|
|