# Nested Sequence of Integers

In some combinatorial research I came across the following nested sequence: $$\{a_n\}=\{1,1,3,1,7,3,17,1,35,7,77,3,157,17,331,1,663,35,1361,7,2729,77,5535,3,11073, \dots\}$$ which is not in the OEIS. The definition for $a_n$ is given by: $$a_n = 2a_{n-2}+a_{n-1} \text{ for } n \equiv 1 \mod 2$$ $$a_n=a_{\hat{n}} \text{ for } n \equiv 0 \mod 2$$ where $\hat{n}$ is the odd part of $n$, i.e. the largest odd number that divides $n$.

Does this look familiar to anyone? Has it shown up anywhere before? References highly appreciated!

There is a related sequence called the semi-Fibonacci, using the Fibonacci relation instead of the $a_{n-1}+2a_{n-2}$ that you use. You can see it in OEIS sequence A030067. It has a number of very interesting combinatorial properties which can be generalised in cases to general two term linear homogeneous recurrence with constant coefficients.
• The "theorem" mentioned in that entry that $a(2n+1)-a(2n-1) = a(n)$ is trivial. By the recurrence, $a(2n+1) = a(2n) + a(2n-1) = a(n)+a(2n-1)$ so the induction was not necessary. – Douglas Zare May 25 '13 at 23:47