1
$\begingroup$

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!

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented May 25, 2013 at 23:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .