<s>[INST] 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.
 [/INST] 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}$.
</s>