Three Simple Rules for Sums
The transformation of sums allows us to simplify a sum closer to our goal. There are three simple rules: distributive law, associate law, and commutative law.
Distributive law allows us to move constants in and out of a \( \sum \)
\[ \sum_{k \in K} ca_k = c \sum_{k \in K} a_k \]
Associative law allows us to break a \( \sum \) into two parts, or to combine two \( \sum \)’s into one.
\[ \sum_{k \in K} (a_k + a_k) = \sum_{k \in K} a_k + \sum_{k \in K} b_k \]
Commutative law allows us to reorder terms into a permutation where the set has no items added, removed, or duplicated
\[ \sum_{k \in K} a_k = \sum_{p\left(k\right) \in K} a_{p\left(k\right)} \]
For example, if K = {-1, 0, +1} and if p(k) = -k, these 3 laws tell us:
Distributive law: \[ ca_{-1} + ca_0 + ca_1 = c\left(a_{-1} + a_0 + a_1\right) \]
Associative law: \[ \left( a_{-1} + b_{-1} \right) + \left( a_ 0 + b_0 \right) + \left( a_1 + b_1 \right) = \left( a_{-1} + a_{0} + a_{1} \right) + \left( b_{-1} + b_{0} + b_{1} \right)\]
Commutative law: \[ a_{-1} + a_0 + a_1 = a_1 + a_0 a_{-1} \]
Here an example of an application of these three basic laws as provided in Concrete Mathematics by GKP:
Let’s computer a general sum of an arithmetic progression: \[S = \sum_{0 \le k \le n} \left(a + bk\right). \]
Commutative law allows us to reorder k with n - k: \[ S = \sum_{0 \le n-k \le n} (a + b(n-k)) = \sum_{0 \le k \le n} \left(a + bn - bk\right) \]
Associative law allows us to break a sum into parts: \[ 2S = \sum_{0 \le k \le n} \left(\left( a+bk \right) + \left(a+bn - bk\right)\right) = \sum_{0 \le k \le n} \left(2a + bn\right) \]
Distributive law allows us move the constant \(2a + bn\) out of the \(\sum\): \[ 2S = \left(2a + bn\right) \sum_{0 \le k \le n} 1 = \left(2a + bn\right)\left(n+1\right) \]
Comments