# Calculate limit on series with nested sum

I want to calculate the limit of following series:

$$\sum_{n=0}^{\infty} \sum_{k=0}^{n} \frac{1}{3^k} \cdot \frac{1}{2^{n-k}}$$

As far I could simply the series to:

$$\sum_{n=0}^{\infty} (\sum_{k=0}^{n} (\frac{1}{3})^k) \cdot (\sum_{k=0}^{n} 2^{n-k})$$

which would then allow me to use the geometric series:

$$\sum_{n=0}^{\infty} (\frac{1-(\frac{1}{3})^{n+1}}{\frac{2}{3}}) \cdot (\sum_{k=0}^{n}2^{n-k})$$

which can even be simplified further to:

$$\sum_{n=0}^{\infty} ((1-(\frac{1}{3})^n\cdot\frac{1}{3})(\frac{3}{2})) \cdot (\sum_{k=0}^{n}2^{n-k})$$

$$\sum_{n=0}^{\infty} (\frac{3}{2}-(\frac{1}{3})^n\cdot\frac{1}{2}) \cdot (\sum_{k=0}^{n}2^{n-k})$$

$$\sum_{n=0}^{\infty} (\frac{1}{2}(3-(\frac{1}{3})^n) \cdot (\sum_{k=0}^{n}2^{n-k})$$

This is as far as I know what to do. The solution by the way is:

$$\sum_{k=0}^{\infty} (\frac{1}{3})^k \sum_{k=0}^{\infty} (\frac{1}{2})^k$$ which could be simplified again with the geometric series.

However I have now idea what to do with $\sum_{k=0}^n2^{n-k}$ though we could write it as $\sum_{k=0}^n 2^n \sum_{k=0}^n 2^{-k}$ this would not make much sense as the former sum would converge against infinity.

• good job showing work! – Irrational Person Jan 8 '15 at 12:42

Let we consider two analytic function on the disk $|z|\leq\frac{3}{2}$: $$f(z) = \sum_{n\geq 0}\frac{z^n}{3^n} = \frac{1}{1-\frac{z}{3}},\qquad g(z) = \sum_{n\geq 0}\frac{z^n}{2^n} = \frac{1}{1-\frac{z}{2}}.\tag{1}$$ Since: $$\sum_{k=0}^{n}\frac{1}{2^k}\cdot\frac{1}{3^{n-k}} = [z^n]\left( f(z)\cdot g(z)\right),\tag{2}$$ it follows that: $$\sum_{n\geq 0}\sum_{k=0}^{n}\frac{1}{2^k}\cdot\frac{1}{3^{n-k}}=\sum_{n\geq 0}[z^n]\left( f(z)\cdot g(z)\right) = \left.\left( f(z)\cdot g(z)\right)\right|_{z=1}=f(1)\cdot g(1),\tag{3}$$ as wanted.

• I don't get where the $\frac{3}{2}$ originates from and what is $[z^n]$? – bodokaiser Jan 8 '15 at 17:00
• @bodokaiser: $\frac{3}{2}$ is just a constant that ensures analyticity over the closed disk (we'll need to evaluate such functions in a neighborhood of $1$), but any constant in the interval $(1,2)$ works just as well. $[z^n]g(z)$ is the standard notation for the coefficient of $z^n$ in the power series given by $g(z)$. – Jack D'Aurizio Jan 8 '15 at 17:04
• So the values you use do not relate to the ones in my example? – bodokaiser Jan 8 '15 at 17:05
• @bodokaiser: that is not what I said. $f(z)$ and $g(z)$ relate with your sums. We have to evaluate them in $z=1$, so it is a good thing to have absolute convergence over disk with radius $>1$. Since the radius of convergence of $f(z)$ is $3$ and the radius of convergence of $g(z)$ is $2$, we can just deal with them as they were analytic functions on the same closed disk, $|z|\leq\frac{3}{2}$. Clear now? – Jack D'Aurizio Jan 8 '15 at 17:43

Let us go to the simplest and the most automatic approach: the change of variables $$(n,k)=(i+j,i)$$ sends the domain $$n\geqslant0,\quad 0\leqslant k\leqslant n,$$ to the domain $$i\geqslant0,\quad j\geqslant0,$$ hence the sum is $$\sum_{i=0}^\infty\sum_{j=0}^\infty\frac1{3^i}\cdot\frac1{2^j}=\sum_{i=0}^\infty\frac1{3^i}\cdot\sum_{j=0}^\infty\frac1{2^j}=\frac1{1-\frac13}\cdot\frac1{1-\frac12}=3.$$

$$\sum^{\infty}_{n=0}\sum^{n}_{k=0}\frac{1}{3^k}\cdot\frac{1}{2^{n-k}}=\sum^{\infty}_{n=0}\sum^{n}_{k=0}\frac{1}{3^k}\cdot\frac{2^k}{2^{n}}=\sum^{\infty}_{n=0}\frac{1}{2^{n}}\sum^{n}_{k=0}\Big(\frac{2}{3}\Big)^k$$ Using the geometric series result for a convergent geometric series yields $$\sum^{\infty}_{n=0}\frac{1}{2^{n}}\sum^{n}_{k=0}\Big(\frac{2}{3}\Big)^k=\sum^{\infty}_{n=0}\frac{1}{2^{n}}\cdot\frac{1-\Big(\frac{2}{3}\Big)^{n+1}}{1-\frac{2}{3}}=3\cdot\sum^{\infty}_{n=0}\frac{1-\Big(\frac{2}{3}\Big)^{n+1}}{2^{n}}=3\cdot\sum^{\infty}_{n=0}\Big(\frac{1}{2^n}-\frac{2}{3}\cdot\frac{1}{3^n}\Big)=3\cdot\sum^{\infty}_{n=0}\frac{1}{2^n}-2\cdot\sum^{\infty}_{n=0}\frac{1}{3^n}=3\cdot\frac{1}{1-1/2}-2\cdot\frac{1}{1-1/3}=6-3=3$$

Hint: $\quad\displaystyle\sum_{k=0}^na^k~b^{n-k}=\frac{a^{n+1}-b^{n+1}}{a-b}\qquad$ and $\qquad\displaystyle\sum_{n=0}^\infty x^n=\frac1{1-x}\quad$ for $|x|<1$.

You have terms like $(\frac{1}{2^n} + \frac{1}{3}\cdot \frac{1}{2^{n-1}} + \cdots + \frac{1}{3^n})$ for each $n$. We can collect terms in $n$ instead of $k$ - we get a series $\frac{1}{3^k} \sum_{i = 0}^\infty 2^{-i}$ for each $k$.

E.g., pick a value of $k$. For $\frac{1}{3^k}$, there exists exactly one term also containing $2^{n-k}$ for any one given positive $n-k$. Collect all these terms to create the sum. We get

$$\sum\sum(\cdots) = \sum_{k = 0}^\infty \frac{1}{3^k}\sum_{n=0}^\infty \frac{1}{2^n} \\ = 2\sum_{k = 1}\frac{1}{3^k} \\ = 2 \frac{1}{1 - \frac{1}{3}} \\ = 3$$

Consider writing the sum as $\sum_{n=0}^{\infty}\dfrac{1}{2^n}\sum_{k=0}^{n}\dfrac{2^k}{3^k}=\sum_{n=0}^{\infty}\dfrac{1}{2^n}\dfrac{1-\dfrac{2^{n+1}}{3^{n+1}}}{1-\dfrac{2}{3}}=\sum_{n=0}^{\infty}\dfrac{1}{2^n}\dfrac{3^{n+1}-2^{n+1}}{3^n}=3\sum_{n=0}^{\infty}\dfrac{1}{2^n}-2\sum_{n=0}^{\infty}\dfrac{1}{3^n}=3(2)-2(\dfrac{3}{2})=3$