Show that recurrence is $O(\phi^{\log n})
Your sequence (shifted by 1) is known as Stern's diatomic sequence, or the Stern–Brocot sequences. The usual recurrence is:
\begin{align}
&amp;a(0)=0 \\ &amp;a(1)=1 \\ &amp;a(2n) = a(n) \\ &amp;a(2n+1) = a(n) + a(n+1)
\end{align}
The recurrence suggests that the answer has something to do with binary representation, so one might be prompted to look at the maximal value of $a(n)$ among numbers of length $m$ in binary:
$$
1,2,3,5,8,13,\ldots
$$
This is the Fibonacci sequence. (One can check that the first maxima are attained at $(2^n-(-1)^n)/3$.)

From here, one immediately sees that the rate of growth is $O(\phi^{\log_2 n})$. 

More can be said. For example, Coons and Tyler determined the best possible constant in front of $\phi^{\log_2 n}$ in their paper The maximal order of Stern's diatomic sequence.

You can find many more links in the OEIS entry A002487.