Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

up vote 1 down vote accepted

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

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

share|improve this answer

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

share|improve this answer

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.