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-3}{2}} + 1)^2 - 2^{\frac{n-1}{2}}(1 - \frac{\sqrt{2}}{2})$

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!