Using summation by parts on a combination

Question

I am trying to expand the series $\sum_{k=1}^{n}\binom{n}{k}$ when $n$ is a integer greater then zero, by using summation by parts. I am using the following definition of summation by parts.\begin{equation} \sum_{k=1}^{n}\Delta V(k)U(k)=V(k)U(k)|_{k=1}^{n+1}-\sum_{k=1}^nV(k)\Delta U(K)\end{equation}When I was expanding the series, I let $U(k)=\binom{n}{k}$ and $\Delta V(k)=1$. My result was the following. \begin{equation}\sum_{k=1}^n\binom{n}{k}=k\binom{n}{k}|_{k=1}^{n+1}-\sum_{k=1}^nk\binom{n}{k}\left(\frac{n-2k-1}{k+1}\right)\end{equation} When I evaluate the first term on the right side I find that I have the factorial of negative one. For instance, when I let $n=1$ I get the following result. \begin{equation}\sum_{k=1}^1\binom{1}{k}=k\binom{1}{k}|_{k=1}^2-\sum_{k=1}^1k\binom{1}{k}\left(\frac{1-2k-1}{k+1}\right)\end{equation} \begin{equation}1=2\binom{1}{2}-1-(-1)\end{equation} \begin{equation}1=\frac{1}{(-1)!}\end{equation} By the last statement the factorial of negative one is implied to be one, but the gamma function says that the factorial of negative one is infinity. Did I make a mistake somewhere or is this just a case that the summation by parts doesn't hold?

Answer 1

I am using the following definition of summation by parts.\begin{equation} \sum_{k=1}^{n}\Delta V(k)U(k)=V(k)U(k)|_{k=1}^{n+1}-\sum_{k=1}^nV(k)\Delta U(K)\end{equation}

Let's sanity-check that by setting $n = 1$: $$\begin{eqnarray} \Delta V(1)U(1) &=& V(2)U(2) - V(1)U(1) - V(1)\Delta U(1) \\ (V(2) - V(1))U(1) &=& V(2)U(2) - V(1)U(1) - V(1)(U(2) - U(1)) \\ V(2)U(1) - V(1)U(1) &=& V(2)U(2) - V(1)U(2) \end{eqnarray}$$

So if, for example, we have $V(1) = 0$ we must also have either $V(2) = 0$ or $U(1) = U(2)$.

Conclusion: you're using an incorrect definition, so it's no wonder you're having problems.

---

If we take the definition from Wikipedia: $$\sum_{k=m}^{n} f_{k} \Delta g_{k} = \left[f_{\color{#C00} n}g_{n+1} - f_{m}g_{m}\right] - \sum _{k=m}^{n \color{#c00} {-1}} g_{k \color{#c00}{+1}}\Delta f_{k}$$ (differences highlighted in colour) and we plug in $m = 1$, $f(k) = \binom{n}{k}$, $g(k) = k-1$, we get $$\begin{eqnarray}\sum_{k=1}^{n} \binom{n}{k} &=& \left[\binom{n}{n} n - \binom{n}{1}0 \right] - \sum _{k=1}^{n-1} k \binom{n}{k}\left( \frac{n-2k-1}{k+1} \right) \\ &=& n - \sum _{k=1}^{n-1} k \binom{n}{k}\left( \frac{n-2k-1}{k+1} \right) \end{eqnarray}$$