Closed form for summation involving binomial coefficients.

Question

how to work following formula

$$f(n) = (n-1)C(n,n) +(n-2)C(n,n-1) + (n-3)C(n,n-2) + \ldots + (2-1)C(n,2)$$

out to following ?

$$f(n) = (n-2)2^{n-1} + 1$$

Answer 1

$(n-r-1)C(n,r-1)$

$=(n-r)C(n,r-1)-C(n,r-1)$

$=\frac{(n-r)n!}{(n-r)! r!}-C(n,r-1)$

$=n\frac{(n-1)!}{(n-1-r))! r!}-C(n,r-1)$

$=nC(n-1,r)-C(n,r-1)$

So,

$\sum_{ 0\le r\le n-1}(n-r-1)C(n,r-1)$

$=\sum_{ 0\le r\le n-1}(nC(n-1,r)-C(n,r-1))$

$=n\sum_{ 0\le r\le n-1}C(n-1,r)-\sum_{ 0\le r\le n-1}C(n,r-1)$

$=n(1+1)^{n-1}-(1+1)^{n}+1$ as $C(n,n)=1$ and $C(n,r)=0$ for $r<0$ or $r>n$

$=(n-2)2^{n-1}+1$

Answer 2

Just use the fact that $\sum_{k=0}^n\binom{n}k=2^n$ and the identity $k\binom{n}k=n\binom{n-1}{k-1}$:

$$\begin{align*} f(n)&=\sum_{k=1}^{n-1}(n-k)\binom{n}{n-k+1}\\ &=\sum_{k=1}^{n-1}k\binom{n}{k+1}\\ &=\sum_{k=2}^n(k-1)\binom{n}k\\ &=\sum_{k=2}^nk\binom{n}k-\sum_{k=2}^n\binom{n}k\\ &=\sum_{k=2}^nn\binom{n-1}{k-1}-\left(2^n-n-1\right)\\ &=n\sum_{k=1}^{n-1}\binom{n-1}k-2^n+n+1\\ &=n\left(2^{n-1}-1\right)-2^n+n+1\\ &=(n-2)2^{n-1}+1 \end{align*}$$

Answer 3

Another way, which is not really different but a bit more compact, uses $f(z)$ where $$ f(z) = \sum_{k=2}^n (k-1) \binom{n}{k} z^{k-2}$$ so that we are interested in $f(1)$.

Formal power series integration yields $$ \int f(z) \; dz = \sum_{k=2}^n \binom{n}{k} z^{k-1} = \frac{1}{z} \left( (z+1)^n - nz - 1 \right)$$

Differentiating, $$ f(z) = -\frac{1}{z^2} \left( (z+1)^n - nz - 1 \right) + \frac{1}{z} \left( n (z+1)^{n-1} - n \right)$$

Now put $z=1$ to get $$ f(1) = -(2^n -n - 1) + n 2^{n-1} - n = (n-2) 2^{n-1} + 1.$$