# Show that recurrence is O(phi^logn)

I have a function whose time complexity is given by the following recurrence:

$$\begin{equation*} T(n) = \begin{cases} \mathcal{O}(1) & \text{for } n=0\ T(k)+T(k-1)+\mathcal{O}(1) & \text{for } n=2k\ T(k)+\mathcal{O}(1) & \text{for } n=2k+1\ \end{cases} \end{equation*}$$

and I have to prove that $$T(n)\in \mathcal{O}(\phi^{log_2 n})$$

Where $$\phi$$ is the golden ratio, $$(1 + \sqrt5)\over2$$

I think I could prove it by induction but, how would I go on about it if I didn’t know that $$T(n)\in \mathcal{O}(\phi^{log_2 n})$$ in the first place?

Thanks!