# Transform double sum $\sum_{i=0}^\infty \sum_{j=0}^i$ to $\sum_{i=0}^\infty \sum_{j=0}^\infty$?

Consider a double sum (assuming it converges)

$$\sum_{i=0}^\infty \sum_{j=0}^i f(i,j)$$

Is there a convenient way to rewrite this sum so that both summations go from zero to infinity $\sum_{i=0}^\infty \sum_{j=0}^\infty$ and the function $f$ arguments are adjusted accordingly? The transformation should be non-trivial, in the sense that no singular functions like step functions should appear. Thanks for any suggestion!

EDIT:

How does the result change for

$$\sum_{i=a}^\infty \sum_{j=b}^i f(i,j)$$

where $a\geq b$?

$$\sum_{i=0}^\infty \sum_{j=0}^\infty f(i+j,j)$$

• Wow, that was easy. Thank you! – Kagaratsch Jun 23 '16 at 20:35
• You are wellcome! – user90369 Jun 23 '16 at 20:37
• Does anything change if $i$ starts with $a$ and $j$ starts with $b$ instead of zero, with $a\geq b$? – Kagaratsch Jun 23 '16 at 20:44
• It's not the same. In the first sum we have an element $f(a,b)$ but not in the alternative sum. – user90369 Jun 23 '16 at 20:56

Thanks to the awesome answer by user90369 I was able to derive the more general result:

$$\sum_{i=a}^N \sum_{j=b}^i f(i,j)=\sum_{j=0}^{a-b-1}\sum_{i=0}^{N-a} f(i+a,j+b)+ \sum_{j=0}^{N-a}\sum_{i=0}^{N-a-j} f(i+j+a,j+a)$$

where $N>>a\geq b$ and it is straightforward to take the limit $N\to \infty$.

EDIT:

Proof via induction

For $N=a$ we have:

$$\sum_{i=a}^a \sum_{j=b}^i f(i,j)=\sum_{j=b}^a f(a,j)$$

as well as

$$\sum_{j=0}^{a-b-1}\sum_{i=0}^{0} f(i+a,j+b)+ \sum_{j=0}^{0}\sum_{i=0}^{-j} f(i+j+a,j+a)=\sum_{j=b}^a f(a,j)$$

such that the proposition holds. Now, assume the proposition is valid for $N$ and investigate how it behaves for $N+1$. The left hand side equals

$$\sum_{i=a}^{N+1} \sum_{j=b}^i f(i,j)=\sum_{j=b}^{N+1} f(N+1,j)+\sum_{i=a}^{N} \sum_{j=b}^i f(i,j)$$

and the right hand side equals

\begin{align} \sum_{j=0}^{a-b-1}\sum_{i=0}^{N+1-a} & f(i+a,j+b)+ \sum_{j=0}^{N+1-a}\sum_{i=0}^{N+1-a-j} f(i+j+a,j+a)=\\ =&\sum_{j=b}^{a-1} f(N+1,j)+ f(N+1,N+1)+ \sum_{j=a}^{N} f(N+1,j)\\ &+\sum_{j=0}^{a-b-1}\sum_{i=0}^{N-a} f(i+a,j+b)+ \sum_{j=0}^{N-a}\sum_{i=0}^{N-a-j} f(i+j+a,j+a) \end{align}

we see that in both cases the excess terms sum up to $\sum_{j=b}^{N+1} f(N+1,j)$, which concludes the induction step and proves the proposition for all $N$.

• A small test - the number of objects is equal: $\frac{N(N+1)}{2}-\frac{a(a-1)}{2}-(b-1)(N-a+1)=(a-b)(N-a+1)+\frac{(N-a+1)(N-a+2)}{2}$. Well done. – user90369 Jun 24 '16 at 9:04
• I also tested this explicitly for up to $N=200$ in Mathematica. The terms agree. – Kagaratsch Jun 29 '16 at 18:27