Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer 1

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|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
add comment

Your Answer

 
discard

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.