# SICP Solutions: Sections 1.2.1 and 1.2.2

## Section 1.2

### Section 1.2.1

#### Exercise 1.9

First procedure:

Second procedure:

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)`

:

So `(A 1 x)`

is \(2^x\).

Expression `(A 2 4)` |
: |

So `(A 2 x)`

is 2 to the power of 2, to the power of 2 .. `x`

times.

Expression `(A 3 3)`

:

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:

Iterative process:

#### Exercise 1.12

We define a procedure `pascal`

that accepts a row and a column as arguments:

#### 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\).