4 minute read

Section 1.2

Section 1.2.1

Exercise 1.9

First procedure:

(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

Second procedure:

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8
(+ 0 9)
9

The first process is a linear recursive process. The second process is a linear iterative process.

Hint: try to see whether calling itself is absolutely the last thing a procedure does.

Exercise 1.10

Expression (A 1 10):

(A 1 10)
(A 0
   (A 1 9))
(A 0
   (A 0
      (A 1 8
(A 0
   (A 0
      (A 0
         (A 1 7))))
(A 0
   (A 0
      (A 0
         (A 0
            (A 1 6)))))
(A 0
   (A 0
      (A 0
         (A 0
            (A 0
               (A 1 5))))))
(A 0
   (A 0
      (A 0
         (A 0
            (A 0
               (A 0
                  (A 1 4)))))))
(A 0
   (A 0
      (A 0
         (A 0
            (A 0
               (A 0
                  (A 0
                     (A 1 3))))))))
(A 0
   (A 0
      (A 0
         (A 0
            (A 0
               (A 0
                  (A 0
                     (A 0
                        (A 1 2)))))))))
(A 0
   (A 0
      (A 0
         (A 0
            (A 0
               (A 0
                  (A 0
                     (A 0
                        (A 0
                           (A 1 1))))))))))
(A 0
   (A 0
      (A 0
         (A 0
            (A 0
               (A 0
                  (A 0
                     (A 0
                        (A 0 2)))))))))
(A 0
   (A 0
      (A 0
         (A 0
            (A 0
               (A 0
                  (A 0
                     (A 0 4))))))))
 (A 0
    (A 0
       (A 0
          (A 0
             (A 0
                (A 0
                   (A 0 8)))))))
 (A 0
    (A 0
       (A 0
          (A 0
             (A 0
                (A 0 16))))))
(A 0
   (A 0
      (A 0
         (A 0
            (A 0 32)))))
(A 0
   (A 0
      (A 0
         (A 0 64))))
(A 0
   (A 0
      (A 0 128)))
(A 0
   (A 0 256))
(A 0 512)
1024

So (A 1 x) is \(2^x\).

Expression (A 2 4) :
(A 2 4)
(A 1
   (A 2 3))
;; So this is 2^(A 2 3), let's see
(A 2 3)
(A 1
   (A 2 2))
;; So 2^(2^(A 2 2))
(A 2 2)
(A 1
   (A 2 1))
;; So 2^(2^(2^(A 2 1)))
(A 2 1)
2
;; So finally 2^(2^(2^2))
;; Or 2^(2^4)
;; Or 2^16
;; 65,636

So (A 2 x) is 2 to the power of 2, to the power of 2 .. x times.

Expression (A 3 3):

(A 3 3)
(A 2
   (A 3 2))
;; We know what (A 2 x) is, 2 to the power of 2 x times.
;; Let's see where (A 3 2) takes us:
(A 3 2)
(A 2
   (A 3 1))
(A 2 2)
;; Which is 2^2
;; and the starting expression is (A 2 4)
;; Which is exactly the same as before.

So again (A 3 3) equals \(2^{16} = 65,636\).

  • (f n) computes \(2n\).
  • (g n) computes \(2^n\).
  • (h n) computes 2 to the power of 2, to the power of 2 .. x times.

Section 1.2.2

Exercise 1.11

Recursive process:

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

(f 4)

Iterative process:

(define (f n)
  (if (< n 3)
      n
      (f-iter 2 1 0 (- n 2))))

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

(f 4)

Exercise 1.12

We define a procedure pascal that accepts a row and a column as arguments:

(define (pascal x y)
  (if (or (= y 0) (= x y))
      1
      (+ (pascal (- x 1) (- y 1))
         (pascal (- x 1) y))))

(pascal 3 2)

Exercise 1.13

First, the induction.

The base step, for \(n = 0\):

\[\mathrm{Fib}(0) = (\phi^0 - \psi^0) / \sqrt{5} = 0 \textrm{, it holds.}\]

Assume it is true for \(n\), we will prove that it is true for \(n + 1\):

\[\begin{align*} \mathrm{Fib}(n+1) &= \frac{\phi^{n+1} - \psi^{n+1}}{\sqrt{5}}\\ \frac{\phi^{n+1} - \psi^{n+1}}{\sqrt{5}} &= \mathrm{Fib}(n) + \mathrm{Fib}(n - 1)\\ \frac{\phi^{n+1} - \psi^{n+1}}{\sqrt{5}} &= \frac{\phi^n - \psi^n}{\sqrt{5}} + \frac{\phi^{n-1} - \psi^{n-1}}{\sqrt{5}}\\ \phi^{n+1} - \psi^{n+1} &= \phi^n - \psi^n + \phi^{n-1} - \psi^{n-1}\\ \phi^{n-1}(\phi^2 - \phi - 1) &= \psi^{n-1}(\psi^2 - \psi - 1) \end{align*}\]

By definition, \(\phi^2 = \phi + 1\). Notice that also \(\psi^2 = \psi + 1\). This means that both sides of the equation are $0$, and the induction holds.

We have proven that

\[\begin{equation*} \mathrm{Fib}(n) = \frac{\phi^n - \psi^n}{\sqrt{5}} \end{equation*}\]

Now we need to prove that \(\vert\frac{\psi^n}{\sqrt{5}}\vert < \frac{1}{2}\).

Notice that \(\psi < \frac{1}{2}\), and hence \(\vert\psi^{n+1}\vert < \vert\psi^n\vert, \forall n \in N\). Since \(\vert\frac{\psi^0}{\sqrt{5}}\vert < \frac{1}{2}\), it holds for all the rest values of \(n\).

Updated: