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