exercise-13.scm (2560B)
1 #! 2 3 *Exercise 1.13:* Prove that _Fib_(n) is the closest integer to 4 [phi]^n/[sqrt](5), where [phi] = (1 + [sqrt](5))/2. Hint: Let 5 [illegiblesymbol] = (1 - [sqrt](5))/2. Use induction and the 6 definition of the Fibonacci numbers (see section *Note 1-2-2::) to 7 prove that _Fib_(n) = ([phi]^n - [illegiblesymbol]^n)/[sqrt](5). 8 9 !# 10 11 #! oh boy. XXX !# 12 13 #! 14 15 ;;; Prove fib(n) = phi^n / sqrt(5). 16 ;;; 17 ;;; First, prove that fib(n) = (phi^n - psi^n) / sqrt(5), where: 18 ;;; phi = (1 + sqrt(5)) / 2, 19 ;;; psi = (1 - sqrt(5)) / 2, 20 ;;; n is a non-negative integer, 21 ;;; fib(0) = 0, 22 ;;; fib(1) = 1, 23 ;;; fib(n) = fib(n - 1) + fib (n - 2). 24 ;;; 25 ;;; Proof by induction: 26 ;;; 27 ;;; For the case where n = 0: 28 ;;; 29 ;;; By definition, fib(0) = 0. 30 ;;; 31 ;;; (phi^0 - psi^0) / sqrt(5) 32 ;;; = (1 - 1) / sqrt(5) 33 ;;; = 0 34 ;;; 35 ;;; For the case where n = 1: 36 ;;; 37 ;;; By definition, fib(1) = 1. 38 ;;; 39 ;;; (phi^1 - psi^1) / sqrt(5) 40 ;;; = (phi - psi) / sqrt(5) 41 ;;; = ((1+sqrt(5))/2 - (1-sqrt(5))/2) / sqrt(5) 42 ;;; = (1/2 + sqrt(5)/2 - 1/2 +sqrt(5)/2) / sqrt(5) 43 ;;; = (2*sqrt(5)/2) / sqrt(5) 44 ;;; = sqrt(5) / sqrt(5) 45 ;;; = 1 46 ;;; 47 ;;; Induction step: 48 ;;; 49 ;;; Assume: 50 ;;; 51 ;;; fib(n) = (phi^n - psi^n) / sqrt(5) 52 ;;; 53 ;;; fib(n-1) = (phi^(n-1) - psi^(n-1)) / sqrt(5) 54 ;;; = (phi^n / phi - psi^n / psi) / sqrt(5) 55 ;;; 56 ;;; fib(n+1) = (phi^(n+1) - psi^(n+1)) / sqrt(5) 57 ;;; = (phi*phi^n - psi*psi^n) / sqrt(5) 58 ;;; = ( (1 + sqrt(5)) * phi^n / 2 - (1 - sqrt(5)) * psi^n / 2) / sqrt(5) 59 ;;; = phi^n / (2 * sqrt(5)) + phi^n / 2 - psi^n / (2 * sqrt(5)) + psi^n / 2 60 ;;; = phi^n / (2 * sqrt(5)) - psi^n / (2 * sqrt(5)) + phi^n / 2 + psi^n / 2 61 ;;; = ((phi^n - psi^n) / sqrt(5)) / 2 + phi^n / 2 + psi^n / 2 62 ;;; = fib(n) / 2 + phi^n / 2 + psi^n / 2 63 ;;; = fib(n) / 2 + (phi^n + psi^n) / 2 64 ;;; XXX: What am I doing here? Is this really acceptable? No circular reasoning? 65 ;;; = fib(n) / 2 + (fib(n) + 2fib(n-1))/2 66 ;;; = fib(n) / 2 + fib(n)/2 + fib(n-1) 67 ;;; = fib(n) + fib(n-1) 68 ;;; 69 ;;; 2 fib(n+1) = fib(n) + phi^n + psi^n 70 ;;; = 2 (fib(n) + fib(n-1)) 71 ;;; fib(n) + phi^n + psi^n = 2fib(n) + 2fib(n-1) 72 ;;; phi^n + psi^n -2fib(n-1) = fib(n) 73 ;;; phi^n + psi^n = fib(n) + 2fib(n-1) 74 ;;; 75 ;;; Now that we know that: 76 ;;; 77 ;;; fib(n) = (phi^n - psi^n) / sqrt(5) 78 ;;; 79 ;;; we can see that at the limit of: 80 ;;; 81 ;;; n -> infinity 82 ;;; 83 ;;; psi^n -> 0 84 ;;; 85 ;;; therefore: 86 ;;; 87 ;;; (phi^n - psi^n) / sqrt(5) -> phi^n / sqrt(5) 88 ;;; 89 ;;; which means that indeed fib(n) is the closest integer to phi^n / sqrt(5) 90 ;;; 91 ;;; QED? 92 93 !#