MA-410 Homework 1

Due at 4:59pm in my mailbox in SAS 3151, Monday, February 7, 2011

All solutions must be submitted in hardcopy either to me in class or placed in my mailbox.
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 ≥ 0 one has
   
   39/50  ((1 + sqrt(5))/2)^n ≥ f_n ≥ 35/50  ((1 + sqrt(5))/2)^n for all n ≥ 2.
   
2. ENT, §1.2, Problem 9 on page 12.
3. ENT, §2.2, Problem 20(a), page 25. Please give a proof based on Euclid's lemma.
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