# 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$.

Updated: