Problem 2

The defining quadratic for $\phi$ gives $\phi^2=\phi+1$. This identity lets us replace two adjacent 1-coefficients at exponents $i+1$ and $i$ by one coefficient at exponent $i+2$.