Find the sum of $\sum_{k=1}^n k(k-1) {{n} \choose {k-1}}$

Question

Find the sum of $$\sum_{k=1}^n k(k-1) {{n} \choose {k-1}}$$

---

The solution in the book is a lot different than what I tried what they did in the book is say $k-1=t$ then they expanded from this point $\sum_{t=0}^{n-1} (t+1)(n) {{n-1} \choose {t-1}}$ and the final answer is $n[(n-1)(2^{n-2}-1)+2^n-2]$ but I did not understand their way as it complicated to me

I thought about using derivatives but I got stuck and I am not sure if it really works I just remember using derivatives for some cases in class and I tried it

$(x+b)^n=$ ${n \choose 0} x^0 b^{n-0}+ {n \choose 1} x^1 b^{n-1} +...+ {n \choose n} x^n b^{n-n} $

derivative with respect to $x$ is

$n(x+b)^n-1=$ $0+ {n \choose 1} b^{n-1} +...+ {n \choose n} nx^{n-1} b^{n-n} $

then derivative again

$n(n-1)(x+b)^n-2=$ $0+0+ {n \choose 2} 2b^{n-2} +...+ {n \choose n} n(n-1)x^{n-2} b^{n-n} $

but I could not continue from here

is it ok to use derivatives ? is there another way other than the book(just expanding)?

thanks for any tips and help!

Answer 1

Since $(1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k$, differentiate twice to get $$n(n-1)(1+x)^{n-2} = \sum_{k=2}^n k(k-1)\binom{n}{k}x^{k-2}$$ Substituting $n+1$ for $n$ we also get $$(n+1)n(1+x)^{n-1} = \sum_{k=2}^{n+1} k(k-1)\binom{n+1}{k}x^{k-2}.$$ Substitute $x=1$ in each of these, giving \begin{align*} n(n-1)2^{n-2} &= \sum_{k=2}^n k(k-1)\binom{n}{k} \\ n(n+1)2^{n-1} &= \sum_{k=2}^{n+1} k(k-1)\binom{n+1}{k}. \end{align*} Subtract the first of these from the second, giving \begin{align*} \tag{*}2^{n-2}n(2(n+1)-(n-1)) &= \sum_{k=2}^{n+1}k(k-1)\left(\binom{n+1}{k}-\binom{n}{k}\right)\\ &= \sum_{k=2}^{n+1}k(k-1)\binom{n}{k-1}. \end{align*} Finally, this gives $$\sum_{k=1}^{n}k(k-1)\binom{n}{k-1} = n2^{n-2}(n+3) - n(n+1)$$ since the summand of (*) is zero for $k=1$ and is $n(n+1)$ for $k=n+1$. The right-hand side indeed simplifies to $$n((n-1)(2^{n-2}-1)+2^n-2).$$

Answer 2

Differentiating $S(x)=\sum_{k=0}^n {n \choose k} x^k$ twice and evaluating at $1,$ you get your sum. But since $S(x) = (1+x)^n,$ you know that differentiating twice and evaluating at $1$ is $n(n-1)2^{n-2}.$

Answer 3

Start with $$ (1+x)^n=\sum_{k=0}^n \binom nk x^k $$ First, multiply both sides by $x$: $$ x(1+x)^n=\sum_{k=0}^n \binom nk x^{k+1}=\sum_{k=1}^{n+1}\binom{n}{k-1}x^k $$ Now you can differentiate twice, then set $x=1$, to recover your sum. $$ \frac{\mathrm d^2}{\mathrm dx^2}\,x(1+x)^n=\sum_{k=1}^{n+1}\binom{n}{k-1}\cdot k\cdot (k-1)\cdot x^{k-2} $$ $$ \frac{\mathrm d^2}{\mathrm dx^2}\,x(1+x)^n\Bigg|_{x=1}=\sum_{k=1}^{\color{red}{n+1}}k(k-1)\binom{n}{k-1} $$ There is one slight problem; the upper limit for the sum we derived is $n+1$, but for the desired sum, the upper limit is $n$. This is fixed by pulling out the $k=n+1$ term from the sum. $$ \frac{\mathrm d^2}{\mathrm dx^2}\,x(1+x)^n\Bigg|_{x=1}=\binom{n}{n}\cdot (n+1)n+\sum_{k=1}^{\color{blue}{n}}k(k-1)\binom{n}{k-1} $$ Now the sum you want has appeared, so you can solve for it and are done (after you compute the second derivative and plug in one).

Answer 4

\begin{align} \sum_{k=1}^n k(k-1) \binom{n}{k-1} &= \sum_{k=2}^n k(k-1) \binom{n}{k-1} \\ &= \sum_{k=2}^n k n \binom{n-1}{k-2} \\ &= n \sum_{k=2}^n (k-2+2)\binom{n-1}{k-2} \\ &= n \sum_{k=2}^n (k-2)\binom{n-1}{k-2} + 2n \sum_{k=2}^n \binom{n-1}{k-2} \\ &= n (n-1) \sum_{k=3}^n \binom{n-2}{k-3} + 2n \sum_{k=2}^n \binom{n-1}{k-2} \\ &= n (n-1) \sum_{k=0}^{n-3} \binom{n-2}{k} + 2n \sum_{k=0}^{n-2} \binom{n-1}{k} \\ &= n (n-1) \left(2^{n-3} - 1\right) + 2n \left(2^{n-2} - 1\right)\\ &= n (n+3) 2^{n-3} - n (n+1) \end{align}

Answer 5

If you are interested, there is a nice alternative solution using combinatorial proof.

Simple Modification to The Equation

Quite trivial to see that the following expression is true:

$$ \sum_{k=1}^{n} k(k-1)\binom{n}{k-1} = 2\sum_{k=1}^{n}\binom{k-1}{2}\binom{n}{k-1} + 2\sum_{k=1}^{n}\binom{k-1}{1}\binom{n}{k-1} $$

First Term in RHS

Choose some people out of a class of $n$ to be committee member. The number of committee member is not fixed, but it is not possible to choose everyone to be in the committee. Then out of the committee, choose two representative. The number of way to do this is given by the following

$$ \sum_{k=1}^{n}\binom{n}{k-1}\binom{k-1}{2} $$

You can also choose the two representatives first, then the rest of the class may or may not join the committee, as long as not everyone join. The number of way to do this is given by the following.

$$ \binom{n}{2}\left(2^{n-2}-1\right) $$

The two expressions count the same thing so they must be equal.

$$ \sum_{k=1}^{n}\binom{n}{k-1}\binom{k-1}{2} = \binom{n}{2}\left(2^{n-2}-1\right) $$

Second Term in RHS

More or less the same as the first term, except only one representative is needed. Choose the committee first, then out of the committee choose one representative. The number of way to do this is given by the following:

$$ \sum_{k=1}^{n}\binom{n}{k-1}\binom{k-1}{1} $$

Or choose the representative first, then the rest of the class may or may not join the committee as long as not everyone join. The number of way to do this is given by the following:

$$ \binom{n}{1}\left(2^{n-1}-1\right) $$

Again, the two expressions count the same thing so they must be equal.

$$ \sum_{k=1}^{n}\binom{n}{k-1}\binom{k-1}{1} = \binom{n}{1}\left(2^{n-1}-1\right) $$

Conclusion

Substitute the two results into the first equation to obtain the solution:

$$ \sum_{k=1}^{n} k(k-1)\binom{n}{k-1} = \binom{n}{2}\left(2^{n-1}-2\right) + \binom{n}{1}\left(2^{n}-2\right) $$

If you prefer, the RHS equals $n\left[(n-1)\left(2^{n-2}-1\right)+2^{n}-2\right]$, consistent with the other answers.