Concrete Mathematics: Manipulation of Sums clarification

Question

For reference this on on page 31 of the first edition of Concrete Mathematics by Graham, Knuth, Patashnik.

Let K be any finite set of integers. The commutative rule for sums is stated as follows: $$\sum_{k\in K}a_k = \sum_{p(k) \in K}a_{p(k)} \tag{2.17}$$

The function $p(k)$ in the general commutative law (2.17) is supposed to be a permutation of all the integers. In other words, for every integer $n$ there should be exactly one integer $k$ such that $p(k)=n$. Otherwise the commutative law might fail. Transformations like $p(k)=k+c$ or $p(k)=c-k$ where $c$ is an integer constant, are always permutations, so they always work.

On the other hand, we can relax the permutation restriction a little bit: We need to require only that there be exactly one integer k with $p(k)=n$ when $n$ is an element of the index set $K$. If $n \notin K$ it doesn't matter how often $p(k)=n$ occurs, because such $k$ don't take part in in the sum. Thus, for example, we can argue that

$$\sum_{\substack{k \in K \\ k \text{ even}}}a_k = \sum_{\substack{n \in K \\ n \text{ even}}}a_n = \sum_{\substack{2k \in K \\ 2k \text{ even}}}a_{2k} = \sum_{2k \in K}a_{2k} \tag{2.19}$$

Since there's exactly one $k$ such that $2k=n$ when $n \in K$ and $n$ is even.

What I don't fully understand is the funtion $p(k)$. It seems like $p$ is sort of like an array containing a permutation of the set $K$ and $p(k)$ is accessing element $k$ of the permutation, and $p$ is the same length as $K$, but I think my understanding of $p(k)$ is flawed and am asking for an explanation of what exactly $p(k)$ is and what the relaxation of the permutation restriction accomplishes.

I also don't see why the authors included $\sum{\substack{n \in K \\ n \text{ even}}}a_n$ in (2.19) as its the same as $\sum{\substack{k \in K \\ k \text{ even}}}a_k$ but using a different variable.

Answer 1

Beginning with "What I don't fully understand is the funtion $p(k)$. It seems like $p$ is sort of like an array containing a permutation of the set $K$ and $p(k)$ is accessing an element $k$ of the permutation, and $p$ is the same length as $K$, but I think my understanding of $p(k)$ is flawed and am asking for an explanation of what exactly $p(k)$ is and what the relaxation of the permutation restriction accomplishes."

The commutative law gives a specific way that you can manipulate addition. When you become adept at using it, it becomes second hand to perform these manipulations, and sometimes quite useful. This is perhaps clearer with the commutative law for multiplication. When I ask my 7 year old daughter what 5x7 is, she laboriously adds 7 to itself 5 times. But she can count by 5's without thinking, so I point out that since 7x5 is the same thing, she can quickly get the same answer with much less work.

The point of "relaxing the permutation restriction" is it allows you to view the commutative law for addition as a special case of more general manipulations, which can be quite useful when you internalize them. The authors then provide an example in the form of "reindexing". Reindexing can be an extremely useful operation when working with sums. Their example shows you how to replace a sum over terms restricted by a set containment and an additional property, namely, being even, by a sum over terms described only by a set containment. This may be viewed as a decrease in complication in describing the terms, or at least a useful alternative way. It should be clear that what they have done is not simply an application of the commutative law -- it's a different way of manipulating sums.

The point of the third paragraph is that the same principle can provide a rationale for many different, useful sum manipulations.

For your more technical question, a permutation $p$ is an invertible map from the integers to itself. A different way to describe this is that for every integer $n$, the equation $p(k) = n$ (viewing $k$ as the unknown) has precisely one solution $k$ -- no more, no fewer. Their broadening is using the map $p(k) = 2k$, i.e., $n = 2k$. Here, the equation $p(k) = n$ has 0 solutions if $n$ is odd, so it does not satisfy the same requirement. But in their example, for each term $a_n$ in the first sum, the subscript $n$ is even, so there is precisely one integer $k$ with $p(k) = n$. This meets the broader requirement they demand of $p$, and makes the manipulation they perform valid.

Without knowing exactly your definition of permutation, it is hard to pinpoint what about your understanding is flawed. But when you say "$p$ is the same length as $K$", that indicates to me an issue. It sounds like you are thinking of a permutation as a specific rearrangement of a finite set, i.e., an ordered list of the elements of that set. The length of the permutation is then the size of the set. But in this context, you must be considering a permutation as a rearrangement of all of the integers, i.e., it's "length" will be infinite.