5

I'm sorry if this seems like a very novice question, but I am still relatively new to the world of discrete math ( still in 9th grade). I've been reviewing some of the concepts I learned in a chapter from Concrete Mathematics (Graham,Knuth,Patashnik) about Sums, and I seem to have completely missed something that threw me off.

I remember going over this problem, so I decided to re-solve it just to make sure I was 100% percent sure I knew those concepts. But, I've been trying to get it for a while and I still cannot find out the answer to my problem.

The problem starts as follows:

\begin{equation} S = \sum_{0 \le k \le n} (a + bk) \end{equation}

Using the commutative law, the index $k$ can be re-written as $n-k$

\begin{equation} S = \sum_{0 \le (n-k) \le n} (a + b(n-k)) \end{equation}

And this can then equal

\begin{equation} S = \sum_{0 \le k \le n} (a + bn-bk) \end{equation}

My question is not as to how we got $a + bn - bk$, but as to why the index can change from $n-k$ to $k$ from the previous equation? Why and how can this be done?

Marc van Leeuwen
  • 115,048
Alejandro
  • 311
  • 1
    Perhaps it might help to think of $k$ only existing within the sum. – Lucas Jun 03 '13 at 02:38
  • 2
    I've put in parentheses, since the summation operator is taken to bind more strongly than $+$ and $-$ operators (so that in $\sum_i i + \sum_j 3j$, the second summation is not contained in the first). Without the parentheses, the expression was meaningless, since $k$ occurred outside of the summation. – Marc van Leeuwen Jun 03 '13 at 04:21
  • @MarcvanLeeuwen thank you for making this question more readable, I didn't take the ()'s into account. – Alejandro Jun 03 '13 at 12:06

3 Answers3

1

It's because $k$ will still take all of the values from 0 to $n$, just in a different (reverse) order and since addition is commutative, this order isn't important.

john
  • 5,633
1

The author's contention seems to be that the two sums listed are the same, as looping over the values in the set $0 \leq n-k \leq n$ is the same as looping over $k$ such that $0 \leq k \leq n$. To see why this is true, we just need to see that the values they loop over are the same. Then, by the commutativity of addition, the order of the values appearing in the sum doesn't matter, so the two sums can be taken to be equal.

Then it is a matter of seeing that if $0 \leq k \leq n$ defines the same set as $0 \leq n-k \leq n$, which we can see as follows:

$k \in \mathbb{N}$ such that $0 \leq k \leq n$ corresponds to the set of values $\{0, 1, 2, \ldots, n-1, n\}$.

$n-k \in \mathbb{N}$, then, such that $0 \leq (n-k) \leq n$, corresponds to the set of values $\{n, n-1, n-2, \ldots, 1, 0\}$.

Clearly, these two sets are the same.

Alex Wertheim
  • 20,278
0

Just want to point out I think the sum is easier to evaluate if you just split it.

S = $\sum\limits_{k=0}^n a + b\sum\limits_{k=0}^n k$ Though your original question is likely more important then any particular sum.

Anthony Deluca
  • 395