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!


I wish this was just a comment, as it's not directly related. I can't comment yet, though.

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.

  • $\begingroup$ 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. $\endgroup$ – Douglas Zare May 25 '13 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.