What's up, Subhasish! (I'm actually the friend Subhasish mentioned to @AmirSagiv)
I got a solution that starts working from the third term. However, it uses a different function for odds and evens.
The first two terms are $1$ and $2$.
Afterwords, odd-indices can be solved with $f(n) = 2^{n-3} + 2^{\frac{n-1}{2}} + 1 = (2^{\frac{n-3}{2}} + 1)^2$
and even-indices with $f(n) = 2^{n-3} + 2^{\frac{n-2}{2}} + 1 = (2^{\frac{n-4}{2}} + 1)^2 + 2^{n-4}$
I believe that there is a way that the two cases can be consolidated into one using modulos or the floor/ceiling functions. So, I may try to do that later.
The first couple terms of the sequence I found with my solution were: $1, 2, 4, 5, 9, 13, 25, 41, 81, 145, 289$.
My solution was a little long, and to be honest, writing math out takes me forever. So I will talk in person with Subhasish (after he wakes up) and some other friends. If we can confirm or disprove my idea then we will edit what I wrote so far.
If anybody online can help to check my work that would be much appreciated as well!