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!