Swapping the order of summation without writing a few terms and guessing the pattern

Question

I am wondering if there is a general way to manipulate double summations, that does not involve writing a few terms and 'guessing' the pattern. For example, consider a polynomial of order $n$: $$ p(x)=\sum_{k=0}^{n} c_k x^k $$ If we shift the argument and use the binomial theorem, we have: \begin{array} .p(x+a) &= \sum\limits_{k=0}^{n} c_k (x+a)^k\\ &= \sum\limits_{k=0}^{n}c_k \sum\limits_{j=0}^{k}\binom{k}{j} a^{k-j} x^j \end{array} Now by writing a few terms and 'guessing' the pattern, I can rewrite this in standard polynomial form, i.e. giving each coefficient of $x^k$: $$ p(x+a)=\sum\limits_{k=0}^{n} x^k \sum\limits_{j=k}^{n}\binom{j}{k} a^{j-k} c_j $$ It seems like we have just swapped $j$ and $k$ in the summands, but is this a false pattern that does not hold in general? The limits on one sum have changed, but not on the other.

Answer 1

It's just the Taylor formula. $$p(x + a) = \sum_{k=0}^n \frac{p^{(k)}(a)}{k!} x^k$$ where $$\frac{p^{(k)}(a)}{k!} = \sum_{j=0}^n c_j \frac{j(j-1)\ldots (j-k+1)}{k!} a^{j-k} = \sum_{j=k}^n c_j {j \choose k} a^{j-k}$$ Note that the terms for $j < k$ have disappeared because they involve a factor of $j - j = 0$.

Answer 2

I think your confusion is the naming of the indices. If you had written your last line with $j$ and $k$ swapped, you would have $$\sum_{j=0}^n x^j \sum_{k=j}^n \binom{k}{j} a^{k-j} c_k.$$

You can easily obtain this expression from your previous line by switching the order of summation. If you draw a "grid" of all possible $(j,k)$ pairs that you are summing over, then one way will sum by rows first, while the other way will sum by columns first. Note that you are basically summing over all $(j,k)$ pairs such that $k \ge j$. So you can either fix $j$ and sum over $k=j,j+1,\ldots, n$, or you can fix $k$ and sum over $j=0,1,2,\ldots,k$.

Answer 3

Where is the "guessing" in this? Here one has a sum $$S=\sum_{k=0}^n\sum_{j=0}^k A_{j,k}$$ where $A_{j,k}={k\choose j}c_ka^{k-j}x^j$ in this particular example. We can write this as $$S=\sum_{j,k\in I}A_{j,k}$$ where $$I=\{(j,k)\in\Bbb Z^2:0\le j\le k\le n\}.$$ For a given $j\in \Bbb Z$, $(j,k)\in I$ iff $j\le k\le n$, and there is such a $k$ iff $0\le j\le n$, so $$S=\sum_{j=0}^n\sum_{k=j}^n A_{j,k}.$$ The variables $j$ and $k$ of summation are "dummy variables" and can be replaced by any other two distinct dummy variables, so we can swap them. Therefore $$S=\sum_{k=0}^n\sum_{j=k}^n A_{k,j}.$$ This is what you've done in your calculation.

Answer 4

Yes, as long as the nested series does converge finitely, you may reorder the summands.

$${\qquad\sum_{k=0}^n c_k\sum_{j=0}^k \binom{k}{j} a^{k-j}x^j\\[1ex] =~\mathop{\sum\qquad}_{(j,k):0\leq j\leq k\leq n} \binom k j c^ka^{k-j}x^j \\[1ex] = ~ \sum_{j=0}^n x^j\sum_{k=j}^n\binom kj c_ka^{k-j} \\ = \sum_{\kappa=0}^n x^\kappa \sum_{\iota=\kappa}^n\binom{\iota}{\kappa}a^{\iota-\kappa}c_\iota}$$

No guesswork involved.