Need help with series definition

Question

This is not a homework problem. I really tried to solve it on my own for some time but haven't gotten far. I suspect this problem may exceed my fairly rusty high-school math. Or, the solution is totally trivial and I just can't see it. I'm looking for a (preferably non-recursive) definition of the following series, which starts at 1:

$$0, \;\frac{1}{2},\; \frac{1}{4}, \;\frac{3}{4},\; \frac{1}{8},\; \frac{3}{8},\; \frac{5}{8},\; \frac{7}{8},\; \frac{1}{16}, \;\ldots$$

(Perhaps $a_1=0$ is an exception and it is better to start with $2$.) The series is obtained from dividing a line into subsequently smaller pieces. In my practical application I need to allocate memory for tasks on a shared stack. Task 1 gets starting position $0$, task 2 position $\frac{s}{2}$, task 3 position $\frac{s}{4}$, and so on, where $s$ is the stack size. The stacksize does not seem to play any role, so I ignore it. The only thing I've gotten so far is this:

If $n-1=2^k$ for integer $k$, then $a_n=\frac{1}{2n-2}$.

If I'm not mistaken, the above condition determines $a_2=\frac{1}{2}$; $a_3=\frac{1}{4}$; $a_5=\frac{1}{8}$; $a_9=\frac{1}{16}$.

But how do I get all the intermediate steps?

I cannot even come up with a recursive definition, let alone a formula that gives me the result without referring to previous results.

Answer 1

It’s convenient to start indexing the sequence at $0$, so that $a_0=0,a_1=\frac12$, and so on. Suppose that $n=2^k+r$, where $0\le r<2^k$; then

$$a_n=\frac{2r+1}{2^{k+1}}\;.$$

For example, $6=2^2+2$, and $a_6=\dfrac{2\cdot2+1}{2^{2+1}}=\dfrac58$.

To find $k$ and $r$ directly from $n$, use binary logarithms; I’ll write $\lg x$ for $\log_2 x$. Then $k=\lfloor\lg n\rfloor$, and $r=n-2^k$, so

$$a_n=\frac{2\left(n-2^{\lfloor\lg n\rfloor}\right)+1}{2^{\lfloor\lg n\rfloor+1}}=\frac{2n+1}{2^{\lfloor\lg n\rfloor+1}}-1\;.$$

Answer 2

$$a(2^n+k)=\frac{2k-1}{2^{n+1}},\quad 1\leqslant k\leqslant 2^n,\quad n\geqslant0$$

Answer 3

Just an interesting way of looking at things: your sequence is a breadth-first search of a binary tree, defined by each node $x$ at level $n$ (root $1/2$ has level $1$) branching into $x \pm 2^{-n - 1}$.