Double summation swap

Question

the solution sheet of an exercice I was working on says in particular:

$$ \sum_{k=0}^{n}\sum_{i=0}^{k}\binom{k}{i}t^ia^{k-i}\alpha_k = \sum_{i=0}^{n}t^i\sum_{k=i}^{n}\binom{k}{i}a^{k-i}\alpha_k $$

I can convince myself of this by spelling out summations on each side, and I think this could probably be proven by induction. But my question is rather: how does one see (or intuit) this relation starting with the LHS? Is there a specific method to be mindful of here?

Thanks

EDIT: In the meantime I found [this thread][1] in a similar vein, whose ticked answer parallels DavidW's here.

$i \leq k$ is same as $ k \geq i$. – Kavi Rama Murthy Oct 22 '20 at 09:58 — Kavi Rama Murthy, Oct 22 '20 at 09:58

score 2 · Answer 1 · answered Oct 22 '20 at 09:58

2

Intuitively best seen by recognizing the double sum as single sum $$\sum_{(i,k)\text{ with }0\le i\le k\le n} $$

answered Oct 22 '20 at 09:58

Hagen von Eitzen

374,180

Interesting! I can see that this works for le LHS, but having a harder time with the RHS. I'll try to work this out. Thanks – Mogu Oct 22 '20 at 10:48

score 1 · Accepted Answer · answered Oct 22 '20 at 10:10

1

Imagine the terms in a matrix indexed by $k$ for rows and $i$ for columns. The right side finds the total by summing along the rows instead of down the columns.

answered Oct 22 '20 at 10:10

DavidW

572

Yes, very nice! Thank you, I will definitely keep that in mind! – Mogu Oct 22 '20 at 10:50
This is sometimes used in numerical analysis. – DavidW Oct 22 '20 at 10:57

score 1 · Answer 3 · answered Oct 22 '20 at 10:19

1

More generally$$\sum_{k=0}^n\sum_{i=0}^ka_{ki}b_ic_{ki}=\sum_{k=0}^n\sum_{i=0}^kb_ia_{ki}c_{ki}=\sum_{0\le i\le k\le n}b_ia_{ki}c_{ki}=\sum_{i=0}^nb_i\sum_{k=i}^na_{ki}c_{ki}.$$

answered Oct 22 '20 at 10:19

J.G.

115,835

That is akin to what Hagen was saying. But ok, it might be worth proving it once and to keep the pattern in mind. This is less about intuition, but that does adress the method aspect of my question! – Mogu Oct 22 '20 at 10:53

Double summation swap

3 Answers3