# Sum - can I just change the terms?

I am looking at an exercise where this sum appears $\sum_{k=0}^{n}\binom{2n+1}{2n+1-k}$, and I saw in my textbook that it should be equal to $\sum_{u=n+1}^{2n+1}\binom{2n+1}{u}$. I replaced at the first sum $2n+1-k$ with $u$, and I get this sum: $\sum_{u=2n+1}^{n+1}\binom{2n+1}{u}$. How did they find the result? Can I just change the terms $n+1$ and $2n+1$, because $n+1$ is smaller?

• A cleaner expression you might find useful is $4^n$. It follows from $\sum\limits_{k=0}^{m} \binom{m}{k} = 2^m$ and symmetry. – G. H. Faust Dec 27 '13 at 22:25
• How can I find with this way the result? – evinda Dec 27 '13 at 22:33
• Ultimately, getting the result for this question is just about changing iterators/bounds in sums, no algebraic identity is likely to help. I just figured this was a small complication amidst another problem where that might be helpful! – G. H. Faust Dec 27 '13 at 22:39

It sometimes helps to write out the terms.

\begin{align*} \sum_{k=0}^n\binom{2n+1}{2n+1-k} &= \binom{2n+1}{2n+1} + \binom{2n+1}{2n} + \dots + \binom{2n+1}{n+2} + \binom{2n+1}{n+1}\\ \\ \sum_{u=n+1}^{2n+1}\binom{2n+1}{u} &= \binom{2n+1}{n+1} + \binom{2n+1}{n+2} + \dots + \binom{2n+1}{2n} + \binom{2n+1}{2n+1}. \end{align*}

So the two sums are the same, they just reverse the order of the summands.

To see this via a change of index, let $u = 2n+1-(n-k)$ so that $u = n+1+k$; as $k$ goes from $0$ to $n$, $u$ goes from $n+1+0 = n+1$ to $n+1+n = 2n+1$. You can think of this as a combination of two index changes, first $w = n - k$ reverses the order of the terms, and then $u = 2n+1-w$ shifts the index.

$\sum_{k=0}^{n}{{2n+1}\choose{2n+1-k}}=\sum_{k=0}^{n}{{2n+1}\choose{k}}=\sum_{k=n+1}^{2n+1}{{2n+1}\choose{k}}$

The first equality holds because it holds for each term. The second equality holds because the sum of the first half of the $2n+2$ coefficients equals the sum of the second half.

Clarification: I assume you know $${{2n+1}\choose{k}} =\frac{(2n+1)!}{k!(2n+1-k)!}=\frac{(2n+1)!}{(2n+1-k)!k!}= {{2n+1}\choose{2n+1-k}}.$$ That's how you get the first equality above. The second equality, comes from the above pairing, but where the terms in the third sum are written in opposite order as in the second sum.

• That is that what I have to show(the second equality).But have I prove that it is valid? – evinda Dec 27 '13 at 22:17

Apllying theorem of smmetry,we have that. $$\sum_{k=0}^{n}\binom{2n+1}{2n+1-k}=\sum_{k=0}^{n}\binom{2n+1}{k}$$ and from $$\sum_{k=0}^{2n+1}\binom{2n+1}{k}=\sum_{k=0}^{n}\binom{2n+1}{k}+\sum_{k=n+1}^{2n+1}\binom{2n+1}{k}$$ follow that $$\sum_{k=0}^{n}\binom{2n+1}{k}=\sum_{k=n+1}^{2n+1}\binom{2n+1}{k}$$

• How did you go from the first line to the second? – evinda Dec 27 '13 at 22:05
• @AdiDani There is an even number of terms. – G. H. Faust Dec 27 '13 at 22:47
• Yes I see is my mistake. I will correct now. – Adi Dani Dec 27 '13 at 22:51