# Simplify $\sum_{k = 0}^n \left[ \binom{m + n + k}{k} 2^{n + 1 - k} - \binom{m + n + k + 1}{k} 2^{n - k} \right]$.

This is Exercise 6 from page 44 of Analysis I by Amann and Escher.

Exercise:

Simplify the sum

\begin{align*} S(m, n) := \sum_{k = 0}^n \left[ \binom{m + n + k}{k} 2^{n + 1 - k} - \binom{m + n + k + 1}{k} 2^{n - k} \right] \end{align*}

for $$m, n \in \mathbb N$$.

Hint: for $$1 \leq j < \ell$$ we have $$\binom{\ell}{j} - \binom{\ell}{j - 1} = \binom{\ell + 1}{j} - 2\binom{\ell}{j - 1}$$.

My attempt:

Unfortunately I don't understand how to use the hint. I don't see how it corresponds with the expression in the sum.

\begin{align*} \sum_{k = 0}^n \Bigg[ \binom{m + n + k}{k} 2^{n + 1 - k} - \binom{m + n + k + 1}{k} 2^{n - k} \Bigg] &= \sum_{k = 0}^n \Bigg[ 2^{n - k} \Big[ \binom{m + n + k}{k} 2 - \binom{m + n + k + 1}{k} \Big] \Bigg]\\ &= \sum_{k = 0}^n \Bigg[ 2^{n - k} \Big[ \binom{m + n + k}{k} + \binom{m + n + k}{k} - \binom{m + n + k + 1}{k} \Big] \Bigg]\\ &= \sum_{k = 0}^n \Bigg[ 2^{n - k} \Big[ \binom{m + n + k}{k} - \binom{m + n + k}{k - 1} \Big] \Bigg] \text{ (Pascal)}. \end{align*}

At this point I'm stuck. I'm not sure if this is a dead end, especially since I didn't use the hint. I appreciate any help.

• Use $\ell = m+n+k$, $j = k$ and ${\ell \choose j} - {\ell +1 \choose j}$ Aug 17 '20 at 1:42

Starting with $$\sum_{k = 0}^n \Bigg[ 2^{n - k} \Big[ \binom{m + n + k}{k} - \binom{m + n + k}{k - 1} \Big] \Bigg],$$ and using the hint with $$\ell=m+n+k$$ and $$j=k$$, we get $$\sum_{k = 0}^n \Bigg[ 2^{n - k} \Big[ \binom{m+n+k+1}{k} - 2\binom{m+n+k}{k - 1} \Big] \Bigg]=\sum_{k = 0}^n\left(2^{n-k}\binom{m+n+k+1}{k}-2^{n-k+1}\binom{m+n+k}{k - 1}\right).$$ This is a telescoping sum, so it can easily evaluated. Namely, letting $$a_k=2^{n-k}\binom{m+n+k+1}{k},$$ then the sum in question is equal to $$\sum_{k=0}^n (a_k-a_{k-1}),$$ which telescopes to $$a_n-a_{-1}$$.
• Thank you for your help. I wrote out the sum so I saw the telescoping action. I have one concern: once the $k - 1$ is introduced (as I did in my original post), doesn't the sum need to start from $k = 1$ instead of $k = 0$? If that is true, then the answer should be $a_n - a_0$, right? Aug 17 '20 at 20:03
• No, the sum still starts from 0. There is nothing wrong with $-1$ in lower index; $\binom{n}{-1}$ is $0$ by definition. Aug 17 '20 at 20:11
• In that case, then the final answer is simply $a_n$? Aug 17 '20 at 20:16