Find the simple closed form of summation from $k=0$ to $N$
I am studying for my discrete mathematics class and I came across a question asking to find the simple closed form of the summation below. I know that $\binom{N}k = \frac{N!}{N!(N-k)!}$ but I am unsure how to use that to find the closed form. I cannot find a simple answer on what a simple closed form is.
$$\sum_{k=0}^N (k^2-k) \binom{N}k $$
Thank you
Solution 1:
-
Simple math show that $k\binom{N}{k}=N\binom{N-1}{k-1}$, so $$\sum_{k=1}^Nk\binom{N}{k}=N\sum_{k=1}^N\binom{N-1}{k-1}=N2^{N-1}$$
-
Using the identity at 1. \begin{eqnarray} k^2\binom{N}{k}=Nk\binom{N-1}{k-1}&=&N(k-1)\binom{N-1}{k-1}+N\binom{N-1}{k-1}\\ &=&N(N-1)\binom{N-2}{k-2}+N\binom{N-1}{k-1} \end{eqnarray} So taking sum over $k^2\binom{N}{k}$ we get $$\sum_{k=1}^Nk^2\binom{N}{k}=N(N-1)\sum_{k=2}^N\binom{N-2}{k-2}+N\sum_{k=1}^N\binom{N-1}{k-1}=2^{N-2}N(N+1)$$ Then the closed form is $2^{N-2}N(N-1)$