7
$\begingroup$

Question:

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?

$\endgroup$
7
  • $\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, 2018 at 12:46
  • 1
    $\begingroup$ $\binom{n}{k}=0$ for $k<0$ and $k>n$, no? $\endgroup$
    – Anvit
    Apr 13, 2018 at 12:47
  • $\begingroup$ Start from $k=1$. For $k=0$ term vanishes as it is. $\endgroup$
    – jeea
    Apr 13, 2018 at 12:49
  • $\begingroup$ No, not really... not for $k<0$ $\endgroup$
    – gt6989b
    Apr 13, 2018 at 12:49
  • $\begingroup$ @gt6989b is there a name or any literatire on it? I'd like to read more $\endgroup$
    – Anvit
    Apr 13, 2018 at 12:51

8 Answers 8

14
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ This might be best answer, albeit of not much help to dear asker. $\endgroup$
    – jeea
    Apr 13, 2018 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, 2018 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, 2018 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, 2018 at 13:01
  • $\begingroup$ Marcus. Very nice, clear.+ $\endgroup$ Apr 13, 2018 at 13:39
9
$\begingroup$

There are $n$ people. You want to select some of them to form a committee. Amongst the committee members, you choose a person to be the president. You also pick from the committee members one person (not necessarily different from the president) to be the treasury. Thus, if the committee consists of $k$ members, then the number of ways to pick the president and the treasury is $k^2$. That is, the total number of ways to pick the committee and the two extra positions is $$\sum_{k=0}^n\,k^2\,\binom{n}{k}\,.$$

On the other hand, you can pick the president and the treasury first. In the case that the president and the treasury are different, there are $n$ ways to choose the president, $n-1$ ways to pick the treasury, and $2^{n-2}$ ways to select the remaining committee members, whence there are $n(n-1)\,2^{n-2}$ ways in total. If the president is the same as the treasury, then there are $n$ ways to choose this person for two positions, and $2^{n-1}$ ways to complete the committee, making $n\,2^{n-1}$ ways in total.

Combining the two ways of counting, we conclude that $$\sum_{k=0}^n\,k^2\,\binom{n}{k}=n(n-1)\,2^{n-2}+n\,2^{n-1}=n(n+1)\,2^{n-2}\,.$$ The claim is now proven.

$\endgroup$
7
$\begingroup$

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}}$$

$\endgroup$
6
$\begingroup$

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).

$\endgroup$
8
  • $\begingroup$ Nice argument!! $\endgroup$ Apr 13, 2018 at 13:02
  • $\begingroup$ That's a nice book! Any other recommendation for UG entrance? $\endgroup$
    – Anvit
    Apr 13, 2018 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, 2018 at 13:14
  • $\begingroup$ @afalsename which exam are you preparing for $\endgroup$
    – jeea
    Apr 13, 2018 at 13:16
  • 1
    $\begingroup$ @jeea explains your name. Also, less competition :P $\endgroup$
    – Anvit
    Apr 13, 2018 at 13:24
3
$\begingroup$

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_i^2=X_i$ so $EX_i^2=EX_i$ 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). $$

$\endgroup$
1
$\begingroup$

Note that $k^2 = k(k-1)+k$. Use this fact together with the following properties of binomials: $$ k \cdot \binom{n}{k} = k \cdot \frac{n!}{k! (n-k)!} = n \cdot \frac{(n-1)!}{(k-1)! (n-k)!} = n \cdot \binom{n-1}{k-1} $$ Similarly: $$ k(k-1) \cdot \binom{n}{k} = n(n-1) \cdot \binom{n-2}{k-2} $$

$\endgroup$
1
  • $\begingroup$ OP has specifically asked for a combinatorial proof. So this won't work for OP. $\endgroup$
    – Anurag A
    Sep 17, 2018 at 20:08
0
$\begingroup$

Hint:

$$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!}$$

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

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}$$

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.