1

The following identity involves a reversal of order of summations. It seems to be correct when I tried through some examples. The sagecell code for verifying some examples is here. But how to give a proof for this? $$\sum\limits_{a=1}^r\sum\limits_{d=1}^a f(a-d,d)+\sum\limits_{a=1}^r f(a,0) =\sum\limits_{d=1}^r\sum\limits_{a=d}^r f(d,a-d)+\sum\limits_{a=1}^r f(0,a)$$

Vishnu Namboothiri K
  • 135

2 Answers2

1

Set $f(0,0)$ as some dummy value, if it is not defined. The LHS can then be written as $$\begin{align*} \sum_{a=1}^r \sum_{d=0}^a f(a-d, d) &= \sum_{a=1}^r \sum_{d=0}^a f(d, a-d) \\ &= \sum_{a=0}^r \sum_{d=0}^a f(d, a-d) - f(0,0) \\ (\ast) &= \sum_{d=0}^r \sum_{a=d}^r f(d, a-d) - f(0,0) \\ &= \sum_{d=1}^r \sum_{a=d}^r f(d, a-d) + \sum_{a=0}^r f(0,a) - f(0,0) \\ &= \sum_{d=1}^r \sum_{a=d}^r f(d, a-d) + \sum_{a=1}^r f(0,a). \end{align*}$$ The equality labelled $(\ast)$ is a classic swap of nested sums. Basically, the double sum iterates over all pairs $(a,d)$ such that $0 \leq d \leq a \leq r$, so the two different conventions represent first fixing $a$, versus first fixing $d$.

catherine
  • 584
  • Thank you for your answer. May I know the reason for the swap of $a-d$ and $d$ in the first step? Is this a standard technique? – Vishnu Namboothiri K Oct 30 '22 at 07:06
  • @VishnuNamboothiriK $\sum_{d=0}^a f(a-d, d) = f(a,0) + f(a-1,1) + f(a-2,2) + \cdots + f(1, a-1) + f(0,a)$ - there is symmetry in the terms. – catherine Oct 30 '22 at 07:09
0

A variation: We obtain \begin{align*} \color{blue}{\sum_{a=1}^r}&\color{blue}{\sum_{d=0}^af(a-d,d)}\tag{1}\\ &=\sum_{a=1}^r\sum_{d=0}^af(d,a-d)\tag{2}\\ &=\sum_{1\leq d\leq a\leq r}f(d,a-d)+\sum_{a=1}^rf(0,a)\tag{3}\\ &\,\,\color{blue}{=\sum_{d=1}^r\sum_{a=d}^rf(d,a-d)+\sum_{a=1}^rf(0,a)}\tag{4} \end{align*} and the claim follows.

Comment:

  • In (1) we merge the sums by starting the index of the inner sum with $d=0$.

  • In (2) we change the order of summation of the inner sum $d\to a-d$.

  • In (3) we separate the sum with $d=0$. We also write the index region of the double sum somewhat more conveniently as preparation for the next step.

  • In (4) we exchange inner and outer sum by setting index limits according to the inequality chain of the index region from (3).

Markus Scheuer
  • 108,315