2
$\begingroup$

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.

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

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}$.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Novice
    Aug 17 '20 at 20:03
  • $\begingroup$ No, the sum still starts from 0. There is nothing wrong with $-1$ in lower index; $\binom{n}{-1}$ is $0$ by definition. $\endgroup$ Aug 17 '20 at 20:11
  • $\begingroup$ In that case, then the final answer is simply $a_n$? $\endgroup$
    – Novice
    Aug 17 '20 at 20:16
  • $\begingroup$ @Novice Exactly $\endgroup$ Aug 17 '20 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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