1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I think your first step uses distributivity and associativity $\endgroup$ – idok Dec 28 '17 at 4:59
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I thought the index manipulation was contemplated under commutative law $\endgroup$ – Francisco José Letterio Dec 28 '17 at 16:07
  • $\begingroup$ @FranciscoJoséLetterio: It depends on the type of index manipulation. If we change the order for instance by replacing $k$ with $n-k$ then we use the commutative law. If we do a simple index shift as it is done here, then we do not apply any algebraic law since the order of summands or other properties do not change. You will better see it, if you write the small special case with $n=2$ without using the sigma symbol. $\endgroup$ – Markus Scheuer Dec 28 '17 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.