MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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