gistfile1.txt

Exercise 1.11

(define (recursive-f n)
  (if (< n 3)
    n
    (+ (recursive-f (- n 1))
                    (* 2 (recursive-f (- n 2)))
		    (* 3 (recursive-f (- n 3))))))


(define (iterative-f n)
  (define (iter-f a b c n)
    (if (= n 0)
        c
	(iter-f b c
	  (+ (* 3 a) (* 2 b) c)
	  (- n 1))))
  (if (< n 3)
      n
      (iter-f 0 1 2 (- n 2))))

Exercise 1.12

(define (pascal-elt row col)
  (cond ((or (<= row 1) (= col 0) (= row col)) 1)
    (else (+ (pascal-elt (- row 1) (- col 1))
             (pascal-elt (- row 1) col)))))

Exercise 1.13

Given the golden ratio = g = 1.6180...
and the conjugate root of the golden ratio = c = -0.6180...

Prove by mathematical induction that Fib(n) is the closest integer to (g^n - c^n)/sqrt(5)

Prove that Fib(0) = (g^0 - c^0)/sqrt(5)
Since a number elevated at 0 is 1, 1 - 1 = 0 and 0 / any number is 0.

Prove that Fib(1) = (g^1 - c^1)/sqrt(5)
1.6180 - -0.6180 is equal to 2.236 and 2.236 / sqrt(5) is equal to 0.00006... which is close to 1.

Prove that Fib(n + 1) = (g^n+1 - c^n+1)/sqrt(5)
Fib(n+1) = Fib(n) + Fib(n-1)
(g^n - c^n)/sqrt(5) + (g^n-1 - c^n-1)/sqrt(5)
((g^n - c^n) + (g^n-1 - c^n-1))/sqrt(5)
(g^n-1(g + 1) - c^n-1(c + 1))/sqrt(5)
((g^n-1)(g^2) - (c^n-1)(c^2))/sqrt(5)
(g^n+1 - c^n+1)/sqrt(5)
I don't know now yet how to prove that (g^n+1 - c^n+1)/sqrt(5) is the closest integer to n