Need help with series definition

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.

-
This is a sequence not a series – mrf Feb 14 '13 at 11:08
@Eric: instead of editing the question to indicate that you have received an useful answer, please consider instead voting up the answers to your question, and marking one of them as the "accepted answer" by clicking on the green check mark. See math.stackexchange.com/about – Willie Wong Feb 14 '13 at 11:25

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\;.$$

-
Unfortunately,I've realized that none of the solutions so far yield the right sequence. – Eric '3ToedSloth' Feb 14 '13 at 18:50
@Eric: They yield the sequence that you described (apart from the initial $0$). Is your description incomplete? – Brian M. Scott Feb 14 '13 at 21:49
Using log_b a = ln a / ln b and starting the sequence from 0, for n=6 I get 13/(2^3.58496250072)-1=0.08333333333 on my calculator, i.e. 1/12 instead of 5/8. I guess I'm doing something wrong, but what? – Eric '3ToedSloth' Feb 16 '13 at 18:20
@Eric: You forgot to take the floor in the denominator. You should have been dividing by $2^3$. – Brian M. Scott Feb 16 '13 at 23:07
Of course, you are completely right. I feel really stupid now. I'll mark the question as answered. Thanks you very much for your help! – Eric '3ToedSloth' Feb 18 '13 at 10:25

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

-

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}$.

-