# Prove that $\sum\limits_{i=1}^{k-1}\sum\limits_{l=1}^{k-i-1}f(i)g(l)=\sum\limits_{i=1}^{k-1}\sum\limits_{l=1}^{i-1}f(l)g(i-l)$

How to prove the following equation for any $k /ge 3$

$$\sum\limits_{i=1}^{k-1}\sum\limits_{l=1}^{k-i-1}f(i)g(l)=\sum\limits_{i=1}^{k-1}\sum\limits_{l=1}^{i-1}f(l)g(i-l)$$

The functions $f$ and $g$ can be arbitrary. the above equation can be seen also as indices for i and l as follow

$$\sum\limits_{i=1}^{k-1}\sum\limits_{l=1}^{k-i-1}[i,l]=\sum\limits_{i=1}^{k-1}\sum\limits_{l=1}^{i-1}[l,i-l]$$

I already tried an algorithm and I found that this equation hold for all $k$ less than or equal 300.

We show the following is valid \begin{align*} \sum_{i=1}^{\color{blue}{k-2}}\sum_{l=1}^{k-1-i}f(i)g(l)=\sum_{\color{blue}{i=2}}^{k-1}\sum_{l=1}^{i-1}f(l)g(i-l) \end{align*}

Observe we can skip in the left-hand series the upper limit $i=k-1$ since then the inner sum $\sum_{l=1}^{0}f(i)g(l)=0$. We also skip in the right-hand series the lower limit $i=1$ since then the inner sum $\sum_{l=1}^0f(l)g(i-l)=0$.

We obtain \begin{align*} \color{blue}{\sum_{i=1}^{k-2}\sum_{l=1}^{k-1-i}f(i)g(l)}&=\sum_{l=1}^{k-2}\sum_{i=1}^{k-1-l}f(l)g(i)\tag{1}\\ &=\sum_{l=1}^{k-2}\sum_{i=l}^{k-2}f(l)g(i-l+1)\tag{2}\\ &=\sum_{1\leq l\leq i\leq k-2}f(l)g(i-l+1)\tag{3}\\ &=\sum_{i=1}^{k-2}\sum_{l=1}^if(l)g(i-l+1)\tag{4}\\ &\color{blue}{=\sum_{i=2}^{k-1}\sum_{l=1}^{i-1}f(l)g(i-l)}\tag{5} \end{align*} and the claim follows.

Comment:

• In (1) we exchange the name of the indices $i$ and $l$.

• In (2) we shift the inner index $i$ to start with $i=l$.

• In (3) we use another representation to better see the index ranges.

• In (4) we exchange the order of summation and start with the series with index $i$ as outer sum.

• In (5) we shift the outer index $i$ to start with $i=2$.

• @YoussefMaouche: You're welcome! :-) – Markus Scheuer Nov 6 '17 at 7:02

This works by a reindexing. But we will be more precise.

Let $S \subset \mathbb N \times \mathbb N$ be such that $(a,b) \in S$, if and only if $f(a)g(b)$ is included in the first sum.

Let $T \subset \mathbb N \times \mathbb N$ be such that if $(c,d) \in T$ if and only if $f(c)g(d)$ appears in the second sum.

If we show that $S = T$, then both summations are the same since we are summing $f(a)g(b)$ over the same subset.

$S$ can be written in roster form as : $S = \{(i,l) : 1 \leq i \leq k-1, 1 \leq l \leq k-i-1\}$.

$T$ can be written in roster form as: $T = \{(m,n-m) : 1 \leq n \leq k-1, 1 \leq m \leq n-1\}$.

We want to show that $S = T$. For this, we will show that $S \subset T$ and $T \subset S$.

To show that $S \subset T$, we note that $(i,l) = (m,n-m)$, then $m=i,l = n-m \implies n = l+i$. Furthermore, since $l\leq k-i-1$, we see that $1 \leq n \leq k+1$, and obviously, $1 \leq i \leq i + l-1$ is true, so $1 \leq m \leq n-1$ is true.Hence, $(i,l) \in T$, so $S \subset T$.

I urge you to show for yourself that $T\subset S$. If you like I will hide the answer here:

For $(m,n-m) \in T$, if we put $(m,n-m) = (i,l)$, then $i=m$ and $l = n-m$. Clearly, $1 \leq i \leq k-1$ is true, and since $1 \leq n \leq k-1$, we see that $1 \leq l+i \leq k+1$ and therefore $1 \leq l \leq k-i-1$. Therefore, $(m,n-m) \in S$.

Therefore, $S=T$ and the sums are the same.

You will see many of these summations in the future. You should get used to change of index (as this is called) as quickly as possible.