Exercise 1.11 -- 1.13

Exercise 1.11

A function $f$ is defined by the rule that

Write a procedure that computes $f$ by means of a recursive process. Write a procedure that computee $f$ by means of an iterative process.

Solution

The recursive process:

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

The itertive process:

(define (fn1 n)
    (define (fn-iter a b c i)
        (if (= n i)
            (+ (* 3 a) (* 2 b) c)
            (fn-iter b c (+ (* 3 a) (* 2 b) c) (+ i 1))))
    (if (< n 3)
        n
        (fn-iter 0 1 2 3)))

Exercise 1.12

The following pattern of numbers is called Pascal’s triangle.

        1
      1   1
    1   2   1
  1   3   3   1
1   4   6   4   1

Write a procedure that computes elements of Pascal’s triangle by means of a recursive process.

Solution

Using the properties of binomial coefficients, which can be expressed as

(define (choose n m)
    (cond ((or (= n m) (= m 0)) 1)
          ((or (= m (- n 1)) (= m 1)) n)
          (else (+ (choose (- n 1) m)
                   (choose (- n 1) (- m 1))))))

Exercise 1.3

Prove that $\text{Fib}(n)$ is the closest integer to $\varphi^n/\sqrt{5}$, where $\varphi = (1 + \sqrt{5})/2$.

Hint: Let $\psi = (1-\sqrt{5})/2$. Use induction and the definition of the Fibonacci numbers to prove that $\text{Fib}(n)= (\varphi^n-\psi^n)/\sqrt{5}$.

Solution

To prove

by induction, we firstly note that the identity is true for $n=0$ and $n=1$.

Next, assuming that the following two equalities hold true

we have

as $\varphi^2=\varphi + 1$ and $\psi^2 = \psi + 1$. Thus we have proved $(\star)$.

Now, noting that $\psi^{n}/\sqrt{5} < 0.5$ for all $n\ge0$ and that $\text{Fib}(n)=(\varphi^n-\psi^n)/\sqrt{5}$ is an integer, we see that $\text{Fib}(n)$ must be the closest integer to $\varphi^n/\sqrt{5}$.