MA-410 Homework 1

Due at 10:15am in class, Monday, February 4, 2005

Solutions may be submitted in person in class, or you may email an ASCII text, html, or postscipt/pdf-formatted document to me.
Note my office hours on my schedule.

1. Prove by induction that for the Fibonacci number f_n, f_0 = f_1 = 1, f_{n+2} = f_{n+1} + f_n for all n ≥ 2 one has
   
   f_n = 1/sqrt(5) ( ((1 + sqrt(5))/2)^(n+1) - ((1-sqrt(5))/2)^(n+1) ).
   (cf. the Binet formula in ENT, §14.3, p.196.)
2. ENT, §1.2, Problem 10, page 12.
3. ENT, §2.2, Problem 14, page 25.
4. ENT, §2.3, Problem 2(d), page 31. Please compute the Bezout coefficients by the extended Euclidean algorithm presented in class, not the back-substitution given in the book.
5. Prove for the extended Euclidean algorithm described in class: s_k t_k+1 - s_k+1 t_k = (-1)^k+1 for all -1 ≤ k ≤ n