Let $n$ be some input to each of the functions we're evaluating. Presume to calculate $i = \lg^{*} n$.
Let $n_i$ be the number less than or equal to 1 that n was reduced to by the iterative logarithm function.
Let $g(n) = 2^n$. Then $g^{(i)} n_i = n$.
Consider:
$$
\begin{align}
\lg (\lg^{*} n)
\end{align}
$$
It is $\lg (\lg^{*} (g^i (n_i))) = \lg i$.
Consider:
$$
\begin{align}
\lg^{*} ( \lg n )
\end{align}
$$
It is $\lg^{*} ( g^{(i-1)} (n_i) ) = i - 1 = θ(i)$.
From 3.24, $\lg i = o(i)$. So:
$$
\begin{align}
\lg (\lg^* n) = o( \lg^* (\lg n) ).
\end{align}
$$
We add the restriction that $n \ge 1$. So the second function is asymptotically larger than the first.
a.
$$
\begin{align}
x^2 &= x + 1 \\
\left(\frac{1 + \sqrt{5}}{2}\right)^2 &= \frac{1 + \sqrt{5}}{2} + 1 \\
\frac{1 + 2\sqrt{5} + 5}{4} &= \frac{1 + \sqrt{5} + 2}{2} \\
\frac{2\sqrt{5} + 6}{4} &= \frac{2 + 2 \sqrt{5} + 4}{4} \\
2 \sqrt{5} + 6 &= 2 \sqrt{5} + 6 \\
2 \sqrt{5} &= 2 \sqrt{5} \\
2 &= 2 \\
1 &= 1
\end{align}
$$
b.
$$
\begin{align}
x^2 &= x + 1 \\
\left( \frac{1 - \sqrt{5}}{2} \right)^2 &= \frac{1 - \sqrt{5}}{2} + 1 \\
\frac{1 - 2 \sqrt{5} + 5}{4} &= \frac{1 - \sqrt{5} + 2}{2} \\
\frac{- 2 \sqrt{5} + 6}{4} &= \frac{2 - 2 \sqrt{5} + 4}{4} \\
-2 \sqrt{5} + 6 &= -2 \sqrt{5} + 6 \\
-2 \sqrt{5} &= -2 \sqrt{5} \\
-2 &= -2 \\
-1 &= -1 \\
1 &= 1 \\
\end{align}
$$
Let's handle the two base cases of $i = 0$ and $i = 1$.
$F_0 = \frac{\phi^0 - \hat{\phi}^0}{\sqrt 5 } = \frac{1 - 1}{\sqrt 5 } = 0$.
$$
\begin{align}
F_1 &= \frac{\phi^1 - \hat{\phi}^1}{\sqrt 5 } \\
&= \frac{\frac{1 + \sqrt 5}{2} - \frac{1 - \sqrt 5}{2}}{\sqrt 5} \\
&= \frac{\frac{2 \sqrt 5}{2}}{\sqrt 5} \\
&= \frac{\sqrt 5}{\sqrt 5} \\
&= 1
\end{align}
$$
Now we perform the induction step. We substitute the expression we're seeking for $F_i$ and $F_{i-1}$ here,
assuming it holds for those Fibonacci numbers.
$$
\begin{align}
F_{i+1} &= F_i + F_{i-1} \\
&= \frac{\phi^i - \hat{\phi}^i}{\sqrt 5} + \frac{\phi^{i-1} - \hat \phi^{i-1}}{\sqrt 5} \\
&= \frac{\phi^i - \hat{\phi}^i + (\phi^{i-1} - \hat \phi^{i-1})}{\sqrt 5} \\
\end{align}
$$
We concern ourselves only with the numerator for a second.
$$
\begin{align}
\phi^i - \hat{\phi}^i + (\phi^{i-1} - \hat \phi^{i-1}) &= \phi^i + \phi^{i-1} - \hat{\phi}^i - \hat{\phi}^{i-1} \\
&= \phi^{i-1}(\phi + 1) - \hat{\phi}^{i-1}(\hat{\phi} + 1)
\end{align}
$$
$\phi + 1$ is:
$$
\begin{align}
\frac{1 + \sqrt 5}{2} + \frac{2}{2} = \frac{3 + \sqrt 5}{2}
\end{align}
$$
This is $\phi^2$:
$$
\begin{align}
\phi^2 &= \left(\frac{1 + \sqrt 5}{2}\right)^2 \\
&= \frac{(1 + \sqrt 5)(1 + \sqrt 5)}{4} \\
&= \frac{1 + 2 \sqrt 5 + 5}{4} \\
&= \frac{6 + 2 \sqrt 5}{4} \\
&= \frac{3 + \sqrt 5}{2}
\end{align}
$$
$\hat{\phi} + 1$ is:
$$
\begin{align}
\frac{1 - \sqrt 5}{2} + \frac{2}{2} &= \frac{3 - \sqrt 5}{2} \\
\end{align}
$$
This is $\hat{\phi}^2$:
$$
\begin{align}
\hat{\phi}^2 &= \left(\frac{1 - \sqrt 5}{2}\right)^2 \\
&= \frac{(1 - \sqrt 5)(1 - \sqrt 5)}{4} \\
&= \frac{1 - 2 \sqrt 5 + 5}{4} \\
&= \frac{6 - 2 \sqrt 5}{4} \\
&= \frac{3 - \sqrt 5}{2}
\end{align}
$$
So our numerator expression becomes $\phi^{i-1}(\phi^2) - \hat{\phi}^{i-1}(\hat{\phi}^2) =
\phi^{i+1} - \hat{\phi}^{i+1}$. Restoring the denominator gives us:
$$
\begin{align}
\frac{\phi^{i+1} - \hat{\phi}^{i+1}}{\sqrt 5} = F_{i+1}
\end{align}
$$
So $F_i = (\phi^i - \hat{\phi}^i) / \sqrt 5$.
