Show that $\sum_{k=0}^n \sum_{l=0}^k t(k, l) =\sum_{l=0}^n \sum_{k=l}^n t(k, l) $.

Question

This is inspired by my answer to $\sum_{k=0}^n \sum_{l=0}^k \binom{n}{k} \binom{k}{l} (-1)^{k-l} s_l ?= \sum_{l=0}^n \sum_{k=l}^n (-1)^{n-k} \binom{n}{k}\binom{k}{l}s_l $.

Show that $\sum_{k=0}^n \sum_{l=0}^k t(k, l) =\sum_{l=0}^n \sum_{k=l}^n t(k, l) $.

Here is my proof using induction.

Let $A(n) =\sum_{k=0}^n \sum_{l=0}^k t(k, l) $ and $B(n) =\sum_{l=0}^n \sum_{k=l}^n t(k, l) $.

Claim:

$A(n) = B(n) $.

Proof.

$A(0) = t(0, 0)$ and $B(0) = t(0, 0) =A(0)$.

$\begin{array}\\ A(n+1) &=\sum_{k=0}^{n+1} \sum_{l=0}^k t(k, l)\\ &=\sum_{k=0}^{n} \sum_{l=0}^k t(k, l)+\sum_{l=0}^{n+1} t(n+1, l)\\ &=A(n)+\sum_{l=0}^{n+1} t(n+1, l)\\ \end{array} $

$\begin{array}\\ B(n+1) &=\sum_{l=0}^{n+1} \sum_{k=l}^{n+1} t(k, l)\\ &=\sum_{l=0}^{n+1} (\sum_{k=l}^{n} t(k, l)+t(n+1, l))\\ &=\sum_{l=0}^{n+1} \sum_{k=l}^{n} t(k, l)+\sum_{l=0}^{n+1} t(n+1, l)\\ &=\sum_{l=0}^{n} \sum_{k=l}^{n} t(k, l)+\sum_{k=n+1}^{n} t(k, l)+\sum_{l=0}^{n+1} t(n+1, l)\\ &=B(n)+\sum_{l=0}^{n+1} t(n+1, l)\\ \end{array} $

Therefore $A(n+1)-A(n) =B(n+1)-B(n)$.

Since $A(0) = B(0)$, then $A(n) = B(n)$ for all $n$.

Answer 1

Here's an alternate proof for this:

Since we know nothing about $t$, we don't really need it at all.

We therefore define $$\phi: P(\mathbb N^2) \to \mathbb R,\qquad M\mapsto \sum_{i\in M} t(i) $$

Using it we can just look at the 2-tuples being created by the sums:

$$ \sum_{k=0}^n \sum_{l=0}^k t(k, l) =\sum_{l=0}^n \sum_{k=l}^n t(k, l) \quad\Leftrightarrow\quad \phi(M_1) = \phi(M_2) $$

Where

\begin{align} M_1 \\&= \bigcup_{k=0}^n \bigcup_{l=0}^k \{(k,l)\} \\&= \{(k,l)\in\mathbb N^2\mid 0\le k \le n \land 0\le l \le k \} \\&= \{(k,l)\in\mathbb N^2\mid 0\le l\le k \le n\} \end{align}

And similarly

\begin{align} M_2 \\&= \bigcup_{l=0}^n \bigcup_{k=l}^n \{(k, l)\} \\&= \{(k,l)\in\mathbb N^2\mid 0\le l \le n \land l\le k \le n \} \\&= \{(k,l)\in\mathbb N^2\mid 0\le l\le k \le n\} \end{align}

And therefore we have $M_1=M_2$