Been trying to prove this identity and lacked the success (or luck) I've tried with induction or some algebra's tricks but ended up stuck over and over. Be happy to get an hint or algebric/combinatoric proof.


Thanks a lot

  • $\begingroup$ Hint: $$3^m = \sum_{j=0}^m \binom{m}{j} 2^j$$ and $$\binom{m}{j} = \frac{m!}{j!(m-j)!}.$$ $\endgroup$ – Daniel Fischer Mar 16 '14 at 20:31

We will establish this equation by counting the number of objects in two different ways. The crux of the problem lies in identifying the objects to be counted and I will try to make this process interesting!!!

Suppose there is a group consisting of $n$ people. They wish to form committees consisting of $k$ people which may be done in $\binom{n}{k}$ ways. After a committee has been formed, a Secretary (S) and Treasurer (T) are chosen, wherein the same guy may be allotted both titles. There are $k^2$ ways of doing this. Later, S and T form a sub committee (which may include themselves) for some task. This sub committee may contain anywhere from $0$ to $k$ members. So, there are $2^k$ ways of doing that. Hence, the total number of ways of choosing a committee, elect a Secretary and Treasurer, and a sub committee equals $\sum_{k=1}^{n} k^2 \binom{n}{k} 2^k$ which is the RHS.

Let's count the same in a different way. Now, we choose S and T in the beginning. Here, there are $2$ cases.

Case 1: Both S and T are allotted to the same person

There are $n$ choices for this person. For the remaining $n-1$ people, we have $3$ choices. $1$: Not in committee and hence sub committee $2$: In committee, but not in sub committee $3$: In committee and sub committee.

So, there are $3^{n-1}$ ways of doing this. And further, S may or may not be in the sub committee. So, in total there are $2n.3^{n-1}$ ways.

Case 2: S and T are allotted to different persons

There are $n(n-1)$ choices for this. For the remaining $n-2$ people, again we have $3$ choices as before. And S and T may or may not include themselves in the subcommittee. So, $4n(n-1)3^{n-2}$ ways here.

Adding the $2$ cases, we get the LHS.

  • $\begingroup$ thank you very much. it's great having a combinatorical proof too, especially because I'm more convenient with the algebric one usually $\endgroup$ – user114138 Mar 17 '14 at 9:03

Start out by using the identity: $$(1 + x)^n - 1 = \sum_{1 \le k \le n}\binom{n}{k} x^k$$

Differentiate both sides with respect to $x$ to get: $$n(1 + x)^{n-1} = \sum_{1 \le k \le n}k \binom{n}{k} x^{k-1}$$. Then multiply both sides by $x$ and get: $$n x (1 + x)^{n-1} = \sum_{1 \le k \le n} k \binom{n}{k} x^k$$. Differentiate both sides again w.r.t to $x$: $$n(1 + x)^{n-1} + n(n-1)x(1 + x)^{n-2} = \sum_{1 \le k \le n} k^2 \binom{n}{k} x^{k-1}$$ Multiply both sides by $x$ again: $$ nx(1 + x)^{n-1} + n(n-1)x^2 (1 + x)^{n-2} = \sum_{1 \le k \le n} k^2 \binom{n}{k} x^k. $$ Finally, put $x = 2$ into this last equation and simplify: $$ 2n \cdot 3^{n-1} + 4n(n-1) \cdot 3^{n-2} = \text{RHS} $$


  • $\begingroup$ We can bring it down by one differentiation by noting that $\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$. $\endgroup$ – André Nicolas Mar 16 '14 at 20:34
  • $\begingroup$ Great! thanksS alot $\endgroup$ – user114138 Mar 17 '14 at 8:59

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.