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!


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)$$

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


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$.

  • 1
    $\begingroup$ 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. $\endgroup$ – user90369 Jun 24 '16 at 9:04
  • $\begingroup$ I also tested this explicitly for up to $N=200$ in Mathematica. The terms agree. $\endgroup$ – Kagaratsch Jun 29 '16 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.