Solving a Limit with Multiple Fractions

[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?

Thank you for your suggestions.

 

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

 

[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?

 

[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)

 

[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.

 

[metacristi]

There is another solution:

Let S[n]=∑ _{k=1 to n} (2k-1)/2^k

S1[n]=∑ _{k=1 to n} k/2^k-1

S2[n]=∑ _{k=1 to n} 1/2^k=1-(1/2)ⁿ

We have:

n=1 ---> S1[1]=1/(2⁰)

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

n=3 ---> S1=11/(2²)

n=4 ---> S1=26/(2³)

n=5 ---> S1=57/(2⁴)

In general S1[n]=a[n]/2^n-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]=2^n-1

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

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

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

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

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

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

But S[n]=S1[n]-S2[n] ---> lim_{n-> ∞} S[n]=3