Combinatoric identity $2n\times3^{n-1}+4n(n-1)3^{n-2}=\sum_{k=1}^{n}k^2\binom{n}{k}2^k$

Question

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.

$$2n\times3^{n-1}+4n(n-1)3^{n-2}=\sum_{k=1}^{n}k^2\dbinom{n}{k}2^k$$

Thanks a lot

Answer 1

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

QED

Answer 2

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.