# Limit of sum

1. Nov 16, 2004

### twoflower

Hi all, I've been fighting with this limit:

$$\lim_{n \rightarrow \infty} \left( \frac{1}{2} + \frac{3}{2^2} + \frac{5}{2^3} + \frac{7}{2^4} + ... + \frac{2n - 1}{2^n} \right)$$

What I did so far:

$$\lim_{n \rightarrow \infty} \left( \frac{1}{2} + \frac{3}{2^2} + \frac{5}{2^3} + \frac{7}{2^4} + ... + \frac{2n - 1}{2^n} \right) = \\ \lim_{n \rightarrow \infty} \left( \frac{1}{2} \left( 1 + \frac{3}{2} + \frac{5}{2^2} + \frac{7}{2^3} + ... + \frac{2n - 1}{2^{n-1}} \right) \right) = \\ \frac{1}{2} \lim_{n \rightarrow \infty} \left( 1 + \frac{3}{2} + \frac{5}{2^2} + \frac{7}{2^3} + ... + \frac{2n - 1}{2^{n-1}} \right)$$

$$\\ = \frac{1}{2} \lim_{n \rightarrow \infty} \left( 1 + \frac{1}{2} \left( 3 + \frac{5}{2} + \frac{7}{2^2} + ... + \frac{2n - 1}{2^{n-2}} \right) \right) = \frac{1}{2} \left( \lim_{n \rightarrow \infty} 1 + \frac{1}{2} \lim_{n \rightarrow \infty} \left( 3 + \frac{5}{2} + \frac{7}{2^2} + ... + \frac{2n - 1}{2^{n-2}} \right) \right) =$$

$$= \frac{1}{2} + \frac{1}{4} \lim_{n \rightarrow \infty} \left( 3 + \frac{5}{2} + \frac{7}{2^2} + ... + \frac{2n - 1}{2^{n-2}} \right) \right) = \frac{1}{2} + \frac{1}{4} \lim_{n \rightarrow \infty} \left( 3 \left( 1 + \frac{5}{6} + \frac{7}{12} + \frac{9}{24} + ... + \frac{2n - 1}{3.2^{n-2}} \right) \right)$$

And with similar adjustments I got this:

$$\frac{1}{2} + \frac{3}{4} + \frac{9}{8} \lim_{n \rightarrow \infty} \left( \frac{5}{9} + \frac{7}{18} + \frac{9}{36} + ... + \frac{4n-2}{9.2^{n-2}} \right) \right)$$

But here I finished .

Do I have the right approach? And if yes, how to complete it? If not, why?

2. Nov 16, 2004

### arildno

Rewrite your initial series as follows:
$$\sum_{i=0}^{n-1}\frac{2i+1}{2^{i+1}}=\sum_{i=0}^{n-1}\frac{i}{2^{i}}+\sum_{i=0}^{n-1}\frac{1}{2^{i+1}}$$
the last sum is a simple, geometric series, which shouldn't pose any problems.

As for the first, use the following trick:
Let:
$$F_{n}(x)=\sum_{i=0}^{n-1}x^{i}, F(x)=\lim_{n\to\infty}F_{n}(x)=\frac{1}{1-x},|x|<1$$
Now, G(x)=xF'(x) equals:
$$G(x)=xF'(x)=x\sum_{i=0}^{\infty}{i}x^{i-1}=\sum_{i=0}^{\infty}ix^{i}$$

Note that your limit is simply $$G(\frac{1}{2})$$
Hence, your solution of the first sum is obtained from:
$$G(x)=x\frac{d}{dx}\frac{1}{1-x}=\frac{x}{(1-x)^{2}}$$

Last edited: Nov 16, 2004
3. Nov 16, 2004

### twoflower

Thank you arildno, very interesting trick. However, this limit was certainly not supposed to be solved using derivatives, because we didn't have them so far. Do you think there is another way to find out this limit?

4. Nov 16, 2004

### arildno

Not that I can think of right now, at least..
It seems rather difficult to do it without the trick mentioned
(I'd be interested if someone comes up with an alternative)

5. Nov 16, 2004

### shmoe

rewrite as:

$$\left( \frac{1}{2} + \frac{3}{2^2} + \frac{5}{2^3} + \frac{7}{2^4} + ... + \frac{2n - 1}{2^n} \right) = \left( \frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^4} + ... + \frac{1}{2^n} \right)+\left( \frac{1}{2} + \frac{2}{2^2} + \frac{3}{2^3} + ... + \frac{n-1}{2^{n-1}} \right)$$

The left sum is just a geometric series, the right sum you can break up as:

$$\left( \frac{1}{2} + \frac{2}{2^2} + \frac{3}{2^3} + ... + \frac{n-1}{2^{n-1}} \right)=\left( \frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + ... + \frac{1}{2^{n-1}} \right)+\left(\frac{1}{2^2} + \frac{1}{2^3} + ... + \frac{1}{2^{n-1}} \right)+ ... +\left(\frac{1}{2^{n-1}} \right)$$

So it becomes a sum of geometric series. Use the usual formula for these and you can end up with a rather nice formula, part of it will be another geometric series and part will go to zero as n goes off to infinity.

6. Nov 17, 2004

### metacristi

There is another solution:

Let S[n]=∑ k=1 to n (2k-1)/2k

S1[n]=∑ k=1 to n k/2k-1

S2[n]=∑ k=1 to n 1/2k=1-(1/2)n

We have:

n=1 ---> S1[1]=1/(20)

n=2 ---> S1=4/(21)

n=3 ---> S1=11/(22)

n=4 ---> S1=26/(23)

n=5 ---> S1=57/(24)

In general S1[n]=a[n]/2n-1

where a[1]=1,a[2]=4,a[3]=11,a[ 4 ]=26,a[5]=57,a[6]=120 ....

Without entering in details (it's enough easy to show this) the recurrence equation of this sequence is:

a[n]-2a[n-1]+a[n-2]=2n-1

The general solution of this (the closed form in 'n' more exactly) has the form:

a[n]=C1+C2*n+C3*2n-1

Solving for n=1,n=2 and n=3 ---> C1=-2 C2=-1 C3=4

Thus a[n]=4*2n-1-(n+2)

Therefore S1[n]=a[n]/2n-1=4-{(n+2)/2n-1}

S2[n]=1-(1/2)n

But S[n]=S1[n]-S2[n] ---> limn-> ∞ S[n]=3

Last edited: Nov 17, 2004