What's up, Subhasish! (I'm actually the friend Subhasish mentioned to @AmirSagiv)

To start off with, the first couple terms of the sequence I found with my solution were: $1, 2, 4, 5, 9, 13, 25, 41, 81, 145, 289$.

I found 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}$

As @SubhasishMukherjee pointed out in a comment, both of these functions can be consolidated into one form using the ceiling function: $f(n) = 2^{n−3} + 2^{\lceil{\frac{n}{2}}\rceil - 1}+1$.

However, the two separated out formulas are meaningful in their own right. Comparing the sequence and the two functions, you can notice some interesting patterns. Every odd-index term is a square, and the difference between an odd index term and the subsequent even-index term is a power of 4. More specifically, starting from the $n=3$ and $n=5$ pair, the powers of 4 are consecutive powers of 4. Both of these patterns have geometric interpretations that can be noticed if you draw out a few more terms of the sequence.

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!