Help with identity proof using sum manipulations

Question

I am currently reading through Graham and Knuth's Concrete Mathematics. The following is Exercise 11 on page 63, about sums:

The general rule (2.56) for summation by parts is equivalent to $$\sum_{0 \le k \lt n} (a_{k+1} -a_k)b_k = a_nb_n - a_0b_0 - \sum_{0 \le k \lt n} a_{k+1}(b_{k+1}-b_k)$$ for $n \ge 0$

Prove this formula directly by using the distributive, associative, and commutative laws.

Here's what I did, I'm just not really sure about the last step

$$\sum_{0 \le k \lt n} (a_{k+1} -a_k)b_k = \sum_{0 \le k \lt n} a_{k+1}b_k - \sum_{0 \le k \lt n}a_kb_k = S_1 - S_2\text{ (by associative law)}$$

Ignoring the first sum for now,

$$S_2 =\sum_{0 \le k \lt n} a_kb_k = \sum_{0 \le k+1 \lt n}a_{k+1}b_{k+1} =\sum_{-1 \le k \lt n-1}a_{k+1}b_{k+1}\text{ (by commutative law)}$$

Now comes the step I'm not so sure of. Since $S_1$ sums from $0 $ to $n-1$ I want an expression for $S_2$ that does the same. That's easy:

$$\sum_{-1 \le k \lt n-1}a_{k+1}b_{k+1} = a_0b_0 + \Biggl( \sum_{0 \le k \lt n-1}a_{k+1}b_{k+1} +a_nb_n \Biggr) -a_nb_n = a_0b_0 -a_nb_n + \sum_{0 \le k \lt n}a_{k+1}b_{k+1} $$

And replacing back when we first got $S_1 - S_2$ and with some extra manipulations we get the formula that we were asked

However, I'm not really sure about the method, since I didn't use the distributive law (I don't know whether the exercise tells us we CAN or we MUST use it) and I'm also doubtful about the mentioned step because removing an element from a sum, creating the terms $a_nb_n$ and $-a_nb_n$ that cancel each other out and then adding one of those as a term of the sum are not contemplated under any of the laws I'm told to use

Is there another way of going around this exercise? Or is what I did OK according to the question?

Thanks in advance.

Edit: Someone pointed out in the comments that I do use the distributive law by taking a $-1$ out of the sum in the first step. So I'm using all three laws. What about the adding and removing terms of a sum?

Answer 1

The derivation should be revised. But at first some general remarks which might be helpful. We should keep in mind that the distributive, commutative and associative law listed in (2.15) to (2.17) \begin{align*} \sum_{k\in K}ca_k&=c\sum_{k\in K}a_k\tag{dist.}\\ \sum_{k\in K}(a_k+b_k)&=\sum_{k\in K}a_k+\sum_{k\in K}b_k\tag{ass.}\\ \sum_{k\in K}a_k&=\sum_{k\in P(K)}a_k\tag{comm.}\\ \end{align*} are not laws of the sigma symbol but just the laws for manipulating the numbers $a_k$ according to the rules of algebra. In order to solve the problem we are free to use one or more of these laws any number of times we consider it to be convenient. We are also allowed to use other admissible transformations like adding zero and represent it as the sum of an element and its additive inverse ($0=a_n-a_n$).

In the following I give a rather detailed derivation applying one rule per step. We obtain \begin{align*} &\color{blue}{\sum_{0\leq k<n}}\color{blue}{(a_{k+1}-a_k)b_k}\\ &\quad=\sum_{0\leq k<n}(a_{k+1}b_k-a_kb_k)\tag{dist.}\\ &\quad=\sum_{0\leq k<n}a_{k+1}b_k+\sum_{0\leq k<n}\left(-a_kb_k\right)\tag{comm.}\\ &\quad=\sum_{0\leq k<n}a_{k+1}b_k-\sum_{0\leq k<n}a_kb_k\tag{dist.}\\ &\quad=\sum_{0\leq k<n}a_{k+1}b_k-\sum_{-1\leq k<n-1}a_{k+1}b_{k+1}\tag{index}\\ &\quad=\sum_{0\leq k<n}a_{k+1}b_k-\left(a_0b_0+\sum_{0\leq k<n-1}a_{k+1}b_{k+1}\right)\tag{ass.}\\ &\quad=\sum_{0\leq k<n}a_{k+1}b_k-\left(a_0b_0+\sum_{0\leq k<n-1}a_{k+1}b_{k+1}\right)+a_nb_n-a_nb_n\tag{+0}\\ &\quad=\sum_{0\leq k<n}a_{k+1}b_k-a_0b_0-\sum_{0\leq k<n-1}a_{k+1}b_{k+1}+a_nb_n-a_nb_n\tag{dist.}\\ &\quad=a_nb_n-a_0b_0-\sum_{0\leq k<n-1}a_{k+1}b_{k+1}-a_nb_n+\sum_{0\leq k<n}a_{k+1}b_k\tag{comm.}\\ &\quad=a_nb_n-a_0b_0-\sum_{0\leq k<n}a_{k+1}b_{k+1}+\sum_{0\leq k<n}a_{k+1}b_k\tag{ass.}\\ &\quad=a_nb_n-a_0b_0-\left(\sum_{0\leq k<n}a_{k+1}b_{k+1}-\sum_{0\leq k<n}a_{k+1}b_k\right)\tag{dist.}\\ &\quad=a_nb_n-a_0b_0-\sum_{0\leq k<n}\left(a_{k+1}b_{k+1}-a_{k+1}b_k\right)\tag{comm.}\\ &\quad\color{blue}{=a_nb_n-a_0b_0-\sum_{0\leq k<n}a_{k+1}\left(b_{k+1}-b_k\right)}\tag{dist.}\\ \end{align*} and the claim follows.

Note:

• It might be useful to go through this problem with a small special case and without sigma notation, for instance with $n=2$ to better see some details.

• The line with (index)-transformation does not apply any algebraic rule, but instead uses the power of the sigma notation to conveniently manipulate summands. If we don't use the sigma notation, then this line and the previous line are identical.