Find $$\sum_{k=0}^n\binom nkk^2$$

I know how to do $$\sum_{k=0}^n\binom nkk=n\space2^{n-1}$$

I tried applying same thing and reached $$\sum_{k=0}^n\binom nkk^2=n\sum_{k=0}^n\binom{n-1}{k-1}k$$

How to proceed?

  • $\begingroup$ Something wrong with the sum on the RHS of last expression, when $k=0$ the binomial coefficient has a negative number in it, since $k-1=-1$... $\endgroup$ – gt6989b Apr 13 '18 at 12:46
  • 1
    $\begingroup$ $\binom{n}{k}=0$ for $k<0$ and $k>n$, no? $\endgroup$ – Anvit Apr 13 '18 at 12:47
  • $\begingroup$ Start from $k=1$. For $k=0$ term vanishes as it is. $\endgroup$ – jeea Apr 13 '18 at 12:49
  • $\begingroup$ No, not really... not for $k<0$ $\endgroup$ – gt6989b Apr 13 '18 at 12:49
  • $\begingroup$ @gt6989b is there a name or any literatire on it? I'd like to read more $\endgroup$ – Anvit Apr 13 '18 at 12:51

From your procedure:

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

The sum is thus similar to

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


Here's one way to do it:

Recall $$(1 + x)^n = \sum_{k = 0}^n \binom{n}{k}x^k.$$

Plugging in $x = 1$ gives that the sum of the binomial coefficients is $2^n$. Notice that $$x \frac{d}{dx} \left(x \frac{d}{dx} \left( (1 + x)^n\right) \right) = \sum_{k = 0}^n k^2 \binom{n}{k} x^k .$$

Computing the left-hand side and evaluating at $x = 1$ will give you the answer.

  • $\begingroup$ This might be best answer, albeit of not much help to dear asker. $\endgroup$ – jeea Apr 13 '18 at 12:57
  • $\begingroup$ @jeea frankly i'm confused which to mark as answer yours or this. Both are great tbh and this was the first approach i tried but just forgot to multiply by x on both sides $\endgroup$ – Anvit Apr 13 '18 at 12:58
  • $\begingroup$ @AFalse Great! If you know this method, then surely adopt this, its much more wider range of application. But do tell me is the answer correct. $\endgroup$ – jeea Apr 13 '18 at 12:59
  • $\begingroup$ @jeea oh its from an entrance exam and we had to do it using induction :P. I was just wondering how to do it without induction $\endgroup$ – Anvit Apr 13 '18 at 13:01
  • $\begingroup$ Marcus. Very nice, clear.+ $\endgroup$ – Peter Szilas Apr 13 '18 at 13:39

You can also give a combinatorial argument (based on A. Engel's book on problem solving): the sum counts the number of ways to choose a committee from a group of $n$ people, and then appoint a chairman and a secretary (where they could be appointed to the same person). If we first choose the chairman and the secretary, we consider two cases. If one person is both chariman and secretary, you can choose him/her in $n$ ways, and then the rest of the committee can be chosen in $2^{n - 1}$ ways. If they are different persons, you can choose them in $n(n - 1)$ ways and then select the rest of the committee in $2^{n - 2}$ ways. This gives $$ n 2^{n - 1} + n(n - 1)2^{n - 2} = n(n + 1)2^{n - 2}. $$ Hence, we have the equality $$ \sum_{k = 0}^n {n \choose k} k^2 = n(n + 1)2^{n - 2}. $$

EDIT: For more examples/information/exercises on combinatorial arguments for this type of sums: Chapter 5 of Engel's Problem-Solving Strategies (you can find a pdf online).

  • $\begingroup$ Nice argument!! $\endgroup$ – Tal-Botvinnik Apr 13 '18 at 13:02
  • $\begingroup$ That's a nice book! Any other recommendation for UG entrance? $\endgroup$ – Anvit Apr 13 '18 at 13:11
  • $\begingroup$ @Tal-Botvinnik Thank you! I always try to find combinatorial arguments, as I find them (in most cases) more elegant than computations, and they give more insight in the problem. $\endgroup$ – P. Senden Apr 13 '18 at 13:14
  • $\begingroup$ @afalsename which exam are you preparing for $\endgroup$ – jeea Apr 13 '18 at 13:16
  • 1
    $\begingroup$ @jeea explains your name. Also, less competition :P $\endgroup$ – Anvit Apr 13 '18 at 13:24

A probabilistic approach.

Let $X_i$ be iid Bernoulli trials with $P(X_i=1)=1/2$ for $i=1,\dotsc,n$. Then $X=X_1+\dotsb+X_n$ follows a Binomial distribution with $n$ trials and probability of success $1/2$ i.e. $$ P(X=k)=\binom{n}{k}2^{-n}\quad(0\leq k\leq n) $$ In particular $EX_i=P(X_i=1)=1/2$, and $X^2=X$ so $EX^2=EX$ and thus $\text{Var}(X_i)=EX_i^2-(EX_i)^2=1/4$ for all $i$. Moreover, $$ \text{Var}(X)=\sum_{i=1}^n\text{Var}(X_i)=n(1/4)=n/4;\quad EX=\sum_{i=1}^nEX_i=n/2 \tag{0} $$ since the $X_i$ are independent and identically distributed.

Notice that $$ EX^2=2^{-n}\sum_{k=0}^n\binom{n}{k}k^2\tag{1} $$ but from (0), we have that $$ EX^2=\text{Var}(X)+(EX)^2=\frac{n(n+1)}{4}\tag{2} $$ whence (1) and (2) imply that $$ \sum_{k=0}^n\binom{n}{k}k^2=2^nEX^2=2^{n-2}n(n+1). $$



$$k^{r+1}=k(k-1)\cdots(k-r)+A_1k(k-1)\cdots(k-r+1)+\cdots+A_rk$$ where $A_i,1\le i\le r$ are arbitrary constants

$$\binom nkk^2=\cdots=\dfrac{n!k(k-1)}{(n-k)!k!}+\dfrac{n!k}{(n-k)!k!}$$


Now use $$(1+1)^m=\sum_{r=0}^m\binom mr$$

Little Generalization:

For $r=2,$ $$k^3=k(k-1)(k-2)+A_1k(k-1)+A_2k$$

$k=1\implies A_2=1,k=2\implies2A_1+2A_2=8$

$$\binom nkk^3=n(n-1)(n-2)\binom{n-3}{k-3}+4n(n-1)\binom{n-2}{k-2}+n\binom{n-1}{k-1}$$




Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.