Café Math : Geometric Series

Hi, this post is for my friend Mrigank who wants to learn about geometric series. His question was: How to understand the following picture ?

Well this is a general fact about series that for any complex number $q$ with $|\,q\,| < 1$ we have, $$ \sum_{n = 0}^\infty q^n = \frac{1}{1-q} $$ The funny gizmo on the left of the equation is the sum symbol, introduced in the work of Leonhard Euler 1707 – 1783, one of the greatest mathematician ever. There are several ways to approach this relation and we shall skim a few of them.

The first approach is to recall that a definition of the sum of a series is by the limit of its partial sums. Namely, $$ \sum_{n=0}^{\infty} a_n \overset{def.}{=} \lim_{N \rightarrow +\infty} \sum_{n = 0}^{N} a_n $$ In our case, $a_n = q^n$ so, $$ \sum_{n=0}^{\infty} q^n = \lim_{N \rightarrow +\infty} \sum_{n = 0}^{N} q^n = \lim_{N \rightarrow +\infty} \frac{1-q^{N+1}}{1-q} = \frac{1}{1-q} $$ provided $q$ is any complex number situated in the unit disc $|\,q\,| < 1$.

An important part of the theory of series is understanding that those object have a life out of convergence issues and existence of limits. The algebraic point of view is to forget that $q$ is a number and to consider it as a letter. The expression, $$ (1-q)(1+q + q^2 + q^3 + \cdots) $$ lives in the ring of formal power series in $q$. There is so much to say about it. But for now, let's say that the product in this ring is well defined and the following computation gives its value, \begin{align*} (1-q)(1+q + q^2 + \cdots) &= (1+q + q^2 + \cdots) - ( q + q^2 + \cdots) = 1 \end{align*} which proves the relation.

Well the picture is interesting in that it gives another approach than the two aforementioned ones. It belongs to the theme of *proofs without words*. Explaining a proof without words is a bit like explaining a joke, it reduces its interest significantly. But as I decided to be kind in this post I'll explain the picture even so.

Ok suppose the area of the big triangle is $1$. We see that the total area of the gray region is $1/3$ because on each horizontal band there is one gray triangle and two white triangles of the same size. Ok now we see that the biggest gray triangle has area $1/4$ and that the next to biggest gray triangle is $1/4$ of $1/4$, which is $1/4^2$ and so on... summing gives the infinite sum.

Even though I find this picture beautiful I don't know if there is a general pattern. That is if there is a way to generalize this reasoning to produce like pictures for other geometric sums.

For those who kindly read this post despite of its unusual simplicity I want to offer a funny math problem.

Problem. Prove that, $$ 7\sum_{n=0}^{\infty}\frac{n^2}{2^n} = 42. $$

There are more advanced aspects beside the mere convergence of the geometric series. One such aspect is given by the celebrated Maclaurin formula, $$ G(z) = \sum_{n \ge 0} G^{(n)}(0) \, \frac{z^n}{n!} $$ which can be seen as the exponential generating series of the sequence, $$ G^{(n)}(0) \overset{def.}{=} \left. \frac{d^n}{dq^n} G(q) \right|_{q=0} $$ of the successive derivatives of $G(q)$ evaluated at $q=0$.

Of course there is no reason to limit oneself to the values at $q=0$. The Taylor formula is interesting in that it gives a way to construct the exponential generating series of the derivative functions, $$ G^{(n)}(q) \overset{def.}{=} \frac{d^n}{dq^n}\, G(q) $$ themselves. A generating series of functions (yum !). Let's see how. The Taylor formula is, $$ G(q+z) = \sum_{n \ge 0} G^{(n)}(q) \,\frac{z^n}{n!} $$

Now let's apply this idea to our example, \begin{align*} G(q+z) &= \frac{1}{1-q-z} \\ &= \frac{1}{1-q} \, \frac{1}{1-\frac{z}{1-q}} \\ &= \frac{1}{1-q} \, \sum_{n \ge 0} \left( \frac{z}{1-q}\right)^n \\ &= \sum_{n \ge 0} \frac{n!}{(1-q)^{n+1}}\,\frac{z^n}{n!} \end{align*} Perfect ! So now, $$ \frac{d^n}{dq^n}\, \frac{1}{1-q} = \frac{n!}{(1-q)^{n+1}} $$ No need to compute the successive derivatives one by one and then guess their general form. No need to then prove by recurrence the result. The general form is there, right before your eyes.

Alfredo De la Fuente posted 2012-04-26 21:07:13

I have the proof for your problem (: I used the tools you taught me. The generating function of the sequence $n^2$ is, $$ G(q) = \sum_{n \ge 0} n^2\, q^n = \frac{q\,(1+q)}{(1-q)^3} $$ By evaluating at $q = \frac{1}{2}$ we get, $$ 7\,G(\tfrac{1}{2}) = 7\,\sum_{n \ge 0} \frac{n^2}{2^n} = 7\,\frac{\tfrac{1}{2}\,\left(1+\tfrac{1}{2}\right)}{\left(1-\tfrac{1}{2}\right)^3} = 42 $$

Samuel VIDAL posted 2012-04-26 21:58:40

Congratulations Alfredo. Let's explain the general technique for those who don't know.
The trick is to use the following differential operator,
$$
\theta = q\,\frac{d}{dq}
$$
called the *Euler operator*. It acts on functions of $q$ by first differentiating with respect to $q$ then multiply the result by $q$. When applied to a monomial $q^n$ it just multiply it by $n$. If applied twice it just multiply it by $n^2$ etc...
\begin{align*}
\theta^k\, q^n &= n^k\, q^n
\end{align*}
So for example if $P(z)$ is a polynomial we have,
$$
P(\theta) \, q^n = P(n)\, q^n
$$
Ok, back to our problem, if we apply the operator $\theta^2$ to both sides of the equation,
$$
\sum_{n \ge 0} q^n = \frac{1}{1-q}
$$
we get,
$$
\sum_{n \ge 0} n^2\, q^n = \frac{q\,(1+q)}{(1-q)^3}
$$
Very nice Alfredo.

Samuel VIDAL posted 2012-04-26 22:43:42

The following table may be useful to handle the general case of a series, $$ G(q) = \sum_{n \ge 0} P(n)\,q^n $$ where $P(n)$ is a polynomial in $n$. One just have to notice that, \begin{align*} \sum_{n \ge 0} P(n)\,q^n = \sum_{n \ge 0} P(\theta)\,q^n = P(\theta)\,\sum_{n \ge 0}q^n = P(\theta)\,\frac{1}{1-q} \end{align*}

Table 1. \begin{align*} \theta\,y&=qy' \\ {\theta}^{2}y&=qy'+{q}^{2}y'' \\ {\theta}^{3}y&=qy'+3\,{q}^{2}y''+{q}^{3}y''' \\ {\theta}^{4}y&=qy'+7\,{q}^{2}y''+6\,{q}^{3}y'''+{q}^{4}y^{(\text{iv})} \\ {\theta}^{5}y&=qy'+15\,{q}^{2}y''+25\,{q}^{3}y'''+10\,{q}^{4}y^{(\text{iv})}+{q}^{5}y^{(\text{v})} \\ {\theta}^{6}y&=qy'+31\,{q}^{2}y''+90\,{q}^{3}y'''+65\,{q}^{4}y^{(\text{iv})}+15\,{q}^{5}y^{(\text{v})}+{q}^{6}y^{(\text{vi})} \\ &\dots \end{align*}

Table 2. Applyed to the case $y = \frac{1}{1-q}$ gives, \begin{align*} \theta\,\,\frac{1}{1-q}&={\frac {q}{ \left( 1-q \right) ^{2}}} \\ {\theta}^{2}\,\frac{1}{1-q}&={\frac {q}{ \left( 1-q \right) ^{2}}}+2\,{\frac {{q}^{2}}{ \left( 1-q \right) ^{3}}} \\ {\theta}^{3}\,\frac{1}{1-q}&={\frac {q}{ \left( 1-q \right) ^{2}}}+6\,{\frac {{q}^{2}}{ \left( 1-q \right) ^{3}}}+6\,{\frac {{q}^{3}}{ \left( 1-q \right) ^ {4}}} \\ {\theta}^{4}\,\frac{1}{1-q}&={\frac {q}{ \left( 1-q \right) ^{2}}}+14\,{\frac {{q}^{2}}{ \left( 1-q \right) ^{3}}}+36\,{\frac {{q}^{3}}{ \left( 1-q \right) ^{4}}}+24\,{\frac {{q}^{4}}{ \left( 1-q \right) ^{5}}} \\ {\theta}^{5}\,\frac{1}{1-q}&={\frac {q}{ \left( 1-q \right) ^{2}}}+30\,{\frac {{q}^{2}}{ \left( 1-q \right) ^{3}}}+150\,{\frac {{q}^{3}}{ \left( 1-q \right) ^{4}}}+240\,{\frac {{q}^{4}}{ \left( 1-q \right) ^{5}}}+120\, {\frac {{q}^{5}}{ \left( 1-q \right) ^{6}}} \\ {\theta}^{6}\,\frac{1}{1-q}&={\frac {q}{ \left( 1-q \right) ^{2}}}+62\,{\frac {{q}^{2}}{ \left( 1-q \right) ^{3}}}+540\,{\frac {{q}^{3}}{ \left( 1-q \right) ^{4}}}+1560\,{\frac {{q}^{4}}{ \left( 1-q \right) ^{5}}}+1800\,{\frac {{q}^{5}}{ \left( 1-q \right) ^{6}}}+720\,{\frac {{q}^{6}}{ \left( 1-q \right) ^{7}}} \\ &\dots \end{align*}

Samuel VIDAL posted 2012-04-29 18:21:34

One more thing... The coefficients appearing in Table 1 are called the *Stirling numbers* of the second kind,
$$
\left\{ n \atop k \right\} = \frac{1}{k!} \sum_{i = 0}^k (-1)^i \left(k \atop i \right) (k-i)^n.
$$
It is the number of ways to partition a labelled set of size $n$ into $k$ unlabeled parts. From that combinatorial remark,
one can produce the generating function for them,
$$
e^{q(e^z-1)} = \sum_{n\ge 0} \left(\sum_{k\ge 0} \left\{ n \atop k \right\} q^k \right)\, \frac{z^n}{n !}
$$
They can get computed easily from the following (Pascal like triangle) relation,
$$
\left\{ n \atop k \right\} = k \left\{ n - 1 \atop k \right\} + \left\{ n - 1 \atop k - 1 \right\}
$$
and the following boundary conditions,
\begin{align*}
\left\{ 0 \atop 0 \right\} &= 1, &
\left\{ n \atop 0 \right\} = \left\{ 0 \atop n \right\} = 0,
\end{align*}
for $n > 0$.

Table 3. (Stirling numbers of the second kind) $$ \begin{array}{rrrrrrrrrrrrrrrr} 1\\ 1&1\\ 1&3&1\\ 1&7&6&1\\ 1&15&25&10&1\\ 1&31&90&65&15&1\\ 1&63&301&350&140&21&1\\ 1&127&966&1701&1050&266&28&1\\ 1&255&3025&7770&6951&2646&462&36&1\\ 1&511&9330&34105&42525&22827&5880&750&45&1\\ 1&1023&28501&145750&246730&179487&63987&11880&1155&55&1\\ 1&2047&86526&611501&1379400&1323652&627396&159027&22275&1705&66&1\\ \end{array} $$

We can also form the exponential generating series of the functions appearing in Table 2.

- From the analysis of the text we have, $$ G(q;z) = \sum_{n\ge 0} \left(\sum_{k\ge 0} k! \left\{ n \atop k \right\} \frac{q^k}{(1-q)^{k+1}} \right)\, \frac{z^n}{n !} $$
- But the following computation gives a very simple expression for this function, \begin{align*} G(q;z) &= \sum_{n \ge 0} \left(\sum_{k\ge 0} k^n \, q^k \right)\, \frac{z^n}{n !} \\ &= \sum_{k \ge 0} q^k \sum_{n\ge 0} \frac{(kz)^n}{n!} \\ &= \sum_{k \ge 0} q^k e^{kz} \\ &= \sum_{k \ge 0} \left( q e^{z} \right)^k \\ &= \frac{1}{1-q \, e^z} \end{align*}

Samuel Vidal posted 2012-05-21 02:38:35

Just a cool link on what we've discussed The Everything Seminar:A Silly Infinite Series .

Check the comment section where people suggested interesting developements too.

Thank You Sir :)