# Interchanging sums with inner sum in terms of outer sum variable

I've got a double sum of the form

$$\sum_{k=0}^\infty \left( \sum_{i=0}^k a_{i,k} \right)$$

and I'm trying to work out how you interchange these two sums. I remember seeing a formula for this in one of my courses, but I can't remember it (nor can I find my notes). As far as I remember, it comes out as two infinite sums.

I know when the inner sum isn't in terms of $k$, you can apply Fubini-Tonelli if the inner summands are all non-negative, but here that obviously doesn't make much sense. I tried to draw a grid with the entries and count them in a different order, but I keep getting the sum indexed by $i$ on the inside so I'm a little lost.

So, if anyone could prod me in the right direction, that would be great.

A good way to remember is to write: $$\sum_{k=0}^\infty \sum_{i=0}^\infty a_{i,k} \chi(i \le k),$$ where $\chi$ represents the indicator function. Then you simply interchange the summation: $$\sum_{k=0}^\infty \left( \sum_{i=0}^k a_{i,k} \right) = \sum_{i=0}^\infty \sum_{k=0}^\infty a_{i,k} \chi(i \le k) = \sum_{i=0}^\infty \sum_{k=i}^\infty a_{i,k}.$$ Obviously, you should be concerned with when you can apply Fubini.

• Thank you! That's a great way of remembering how to do this – ribbcastle Dec 13 '16 at 11:57

A slightly different notation:

\begin{align*} \sum_{k=0}^\infty\left(\sum_{i=0}^k a_{i,k}\right)=\sum_{\color{blue}{0\leq i\leq k<\infty}}a_{i,k}=\sum_{i=0}^\infty\left(\sum_{k=i}^\infty a_{i,k}\right) \end{align*}

Instead of directly switching the sums, you can use an intermediate step with only one sum, for example:

$$\sum_{i=1}^{\infty}\sum_{j=1}^{i}f\left(\left(i,j\right)\right)\\ = \sum_{t\in\left\{ \left(i,j\right)\mid j\le i\le \infty\right\} }f\left(t\right)\\ = \sum_{j=1}^{\infty}\sum_{i=j}^{\infty}f\left(\left(i,j\right)\right)$$

This has the advantage that it works with pretty much arbitrary amounts of nested summations and it's also easier.

You can simply write the terms as

\begin{align} \sum_{k=0}^\infty \sum_{i=0}^k a_{i,k} &= \color{blue}{a_{0,0}}\\ &\ + \color{blue}{a_{0,1}} + \color{green}{a_{1,1}}\\ &\ + \color{blue}{a_{0,2}} + \color{green}{a_{1,2}} + \color{red}{a_{2,2}}\\ &\ + \dots\\ \end{align}

and this suggests reordering in a form \begin{align} \sum_{k=0}^\infty \sum_{i=0}^k a_{i,k} &= (\color{blue}{a_{0,0}}+ \color{blue}{a_{0,1}} + \color{blue}{a_{0,2}}+\dots) \\ &\ + (\color{green}{a_{1,1}} + \color{green}{a_{1,2}} + \color{green}{a_{1,3}} + \dots)\\ &\ + (\color{red}{a_{2,2}} + \color{red}{a_{2,3}} + \color{red}{a_{2,4}} + \dots)\\ &\ + \dots\\ &= \sum_{i=0}^\infty \sum_{k=i}^\infty a_{i,k} \end{align}