4
$\begingroup$

Empirically, these $2$ sums are supposed to be equal:

$$\sum_{k=0}^n \sum_{j=0}^k a_j b_{k-j} = \sum_{k=0}^n a_k \sum_{j=0}^{n-k} b_j$$

I failed to prove it with a "change of index" and now I am thinking the only possible way to solve this is to use $\sum _{i+j \leq n}$ which has always been a true nightmare for me.

Here is my unfruitful work: $$ \sum_{k=0}^n \sum_{j=0}^k a_j b_{k-j} = \sum_{k=0}^n \sum_{j=k}^0 a_{k-j} b_j$$

$\endgroup$
4
  • $\begingroup$ Shouldn't it suffice to use the change of index $j' := k - j$? $\endgroup$
    – Bruno B
    Commented Mar 13, 2023 at 20:06
  • $\begingroup$ @BrunoB it requires an additional step as the first sum has $a_j$ and the second $a_k$ $\endgroup$
    – Henry
    Commented Mar 13, 2023 at 20:17
  • 1
    $\begingroup$ @BrunoB Probably not. The sum really is $\sum_{0\le i,j, i+j\le n}a_ib_j$ and the first double sum adds the "diagonals" while the second one adds the "horizontals". The OP may be right that they should switch to a single sum. $\endgroup$
    – user700480
    Commented Mar 13, 2023 at 20:19
  • $\begingroup$ Thanks for indicating my errors, I should have been more careful. $\endgroup$
    – Bruno B
    Commented Mar 13, 2023 at 20:27

3 Answers 3

4
$\begingroup$

$$\begin{array}{cll}&\sum_{k=0}^{n}\sum_{j=0}^ka_jb_{k-j}\\=&\sum_{j=0}^{n}\sum_{k=j}^na_jb_{k-j}&\text{Swap sums, }j\le k\iff k\ge j\\=&\sum_{j=0}^{n}\sum_{k=0}^{n-j}a_jb_k&\text{Substitution }k\to k-j\\=&\sum_{k=0}^{n}\sum_{j=0}^{n-k}a_kb_j&\text{Swap letters }k\text{ and }j\\=&\sum_{k=0}^{n}a_k\sum_{j=0}^{n-k}b_j&\text{Extract }a_k\text{ in front of the second sum}\end{array}$$

$\endgroup$
2
$\begingroup$

A variation. We obtain \begin{align*} \color{blue}{\sum_{k=0}^n\sum_{j=0}^ka_jb_{k-j}} &=\sum_{0\leq j\leq k\leq n}a_jb_{k-j}\tag{1}\\ &=\sum_{j=0}^n\sum_{k=j}^na_jb_{k-j}\tag{2}\\ &=\sum_{j=0}^n\sum_{k=0}^{n-j}a_jb_{k}\tag{3}\\ &\,\,\color{blue}{=\sum_{k=0}^n\sum_{j=0}^{n-k}a_kb_j}\tag{4} \end{align*} and the claim follows.

Comment:

  • In (1) we write the index region conveniently to better see what's going on.

  • In (2) we exchange the sums.

  • In (3) we shift the index to start with $k=0$.

  • In (2) we finally swap $k$ and $j$.

$\endgroup$
1
$\begingroup$

You can display it expanding the sum $\sum\limits_{k=0}^n \sum\limits_{j=0}^k a_j b_{k-j}$ into a table. Start with each row being a different $k$ and each column a different $j$ to get

$$\begin{matrix} a_0b_0 &+ & & & & &\\ a_0b_1 &+ & a_1b_0 &+ & & &\\ a_0b_2 &+ & a_1b_1 &+ & a_2b_0 & +&\\ \cdots & &\cdots & &\cdots & & \ddots & \\ a_0b_{n-1} &+ & a_1b_{n-2} &+ & a_2b_{n-3} &+& \cdots &+& a_{n-1}b_0&+\\ a_0b_n &+ & a_1b_{n-1} &+ & a_2b_{n-2} &+& \cdots &+& a_{n-1}b_1 &+& a_nb_0\\ \end{matrix}$$

Then read the same expansion with each column being a separate $k$ and then for each $k$ the non-empty rows (so starting one lower each time) being a separate $j$ and you get $\sum\limits_{k=0}^n a_k \sum\limits_{j=0}^{n-k} b_j$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .