13.6: Double Trouble

Last updated
Save as PDF

Page ID: 48391

Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
Google and Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Sometimes we have to evaluate sums of sums, otherwise known as double summations. This sounds hairy, and sometimes it is. But usually, it is straightforward— you just evaluate the inner sum, replace it with a closed form, and then evaluate the outer sum (which no longer has a summation inside it). For example,⁵

\[\begin{aligned} \sum_{n=0}^{\infty}\left( y^n \sum_{i=0}^{n} x^i\right) &= \sum_{n=0}^{\infty} \left( y^n \dfrac{1 - x^{n+1}}{1-x} \right) & \text{equation 13.2} \\ &= \dfrac{1}{1-x} \sum_{n=0}^{\infty} y^n - \left( \dfrac{1}{1-x} \right)\sum_{n=0}^{\infty} y^n x^{n+1} \\ &= \dfrac{1}{(1-x)(1-y)} - \left( \dfrac{x}{1-x} \right) \sum_{n=0}^{\infty} (xy)^n & \text{Theorem 13.1.1} \\ &= \dfrac{1}{(1-x)(1-y)} - \dfrac{x}{(1-x)(1-xy)} & \text{Theorem 13.1.1} \\ &= \dfrac{(1-xy)-x(1-y)}{(1-x)(1-y)(1-xy)} \\ &= \dfrac{1-x}{(1-x)(1-y)(1-xy)} \\ &= \dfrac{1}{(1-y)(1-xy)}. \end{aligned}\]

When there’s no obvious closed form for the inner sum, a special trick that is often useful is to try exchanging the order of summation. For example, suppose we want to compute the sum of the first \(n\) harmonic numbers

\[\label{13.6.1} \sum_{k=1}^{n} H_k = \sum_{k=1}^{n} \sum_{j=1}^{k} \dfrac{1}{j}\]

For intuition about this sum, we can apply Theorem 13.3.2 to equation 13.4.3 to conclude that the sum is close to

\[\nonumber \int_{1}^{n} \ln(x) dx = x \ln (x) - x \bigg|_{1}^{n} = n \ln (n) - n + 1.\]

Now let’s look for an exact answer. If we think about the pairs \((k, j)\) over which we are summing, they form a triangle:

The summation in Equation \ref{13.6.1} is summing each row and then adding the row sums. Instead, we can sum the columns and then add the column sums. Inspecting the table we see that this double sum can be written as

\[\begin{align} \nonumber \sum_{k=1}^{n} H_k &= \sum_{k=1}^{n} \sum_{j=1}^{n} \dfrac{1}{j} \\ \nonumber &= \sum_{j=1}^{n} \sum_{k=j}^{n} \dfrac{1}{j} \\ \nonumber &= \sum_{j=1}^{n} \dfrac{1}{j} \sum_{k=j}^{n} 1 \\ \nonumber &= \sum_{j=1}^{n} \dfrac{1}{j} (n-j+1) \\ \nonumber &= \sum_{j=1}^{n} \dfrac{n+1}{j} - \sum_{j=1}^{n} \dfrac{j}{j} \\ \nonumber &= (n + 1)\sum_{j=1}^{n} \dfrac{1}{j} - \sum_{j=1}^{n} 1 \\ &= (n+1) H_n - n. \end{align}\]

⁵OK, so maybe this one is a little hairy, but it is also fairly straightforward. Wait till you see the next one!