Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Perhaps it might help to think of $k$ only existing within the sum. –  Lucas Jun 3 '13 at 2: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 3 '13 at 4:21
    
@MarcvanLeeuwen thank you for making this question more readable, I didn't take the ()'s into account. –  Alejandro Lucena Jun 3 '13 at 12:06

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks for such a clear explanation. I completely understand it now. :) –  Alejandro Lucena Jun 3 '13 at 2:36
    
My pleasure, glad I could help! –  AWertheim Jun 3 '13 at 2:36

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.

share|improve this answer
    
Thank you @john! –  Alejandro Lucena Jun 3 '13 at 2:37
    
no problem at all. –  john Jun 3 '13 at 2:38

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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