# Combinatorial proof for an identity

I'm trying to show the equality below using a combinatorial argument. For the left hand side; suppose there are n lands to build houses that can hold 3 families at once. First it counts the ways of building houses with n choose k in summation and then for each case of houses it puts 3 family inside those k houses. If I algebraically change right hand side getting a slightly longer equation, I can show that they are counting the same thing. However, I should be able to do so without changing the right hand side with algebraic manipulations. Can someone help me find the story of the right hand side?

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

There are 3 cases.

Case 1: The families occupy $$1$$ house.

There are $$n$$ ways to choose the land to build the occupied house.

For the remaining $$n-1$$ lands, a house can be built or not to be built, so there are $$2^{n-1}$$ ways.

Hence, there are $$n\cdot 2^{n-1}$$ ways for Case 1.

Case 2: The families occupy $$2$$ houses.

There are $$n$$ ways to choose the land to build the occupied house for $$2$$ families and then there are $$n-1$$ ways to choose the land to build the occupied house for $$1$$ family.

Then there are $${3 \choose 2}=3$$ ways to choose $$2$$ families for the occupied house for $$2$$ families and the remaining $$1$$ family for the occupied house for $$1$$ family.

For the remaining $$n-2$$ lands, a house can be built or not to be built, so there are $$2^{n-2}$$ ways.

Hence, there are $$n(n-1)\cdot 3\cdot 2^{n-2}=3n(n-1)\cdot 2^{n-2}$$ ways for Case 2.

Case 3: The families occupy $$3$$ houses.

There are $$n$$ ways to choose the land to build the occupied house for the $$1$$st family, then there are $$n-1$$ ways to choose the land to build the occupied house for the $$2$$nd family and there are $$n-2$$ ways to choose the land to build the occupied house for the $$3$$nd family.

For the remaining $$n-3$$ lands, a house can be built or not to be built, so there are $$2^{n-3}$$ ways.

Hence, there are $$n(n-1)(n-2)\cdot 2^{n-3}$$ ways for Case 3.

Combining the 3 cases

\begin{align*} \text{The total number of ways} & =n\cdot 2^{n-1}+3n(n-1)\cdot 2^{n-2}+n(n-1)(n-2)\cdot 2^{n-3} \\ & =n[4+6(n-1)+(n-1)(n-2)]\cdot 2^{n-3} \\ & =n^2(n+3)\cdot 2^{n-3} \\ \end{align*}

• I did this also but doesn't this include algebraic manipulation though? I wrote about this is in the explanation and I wasn't sure whether I could use this, whether it clashes with the idea of combinatorial proof. I'm just asking because I am not sure. – Stefan M. May 17 at 15:19

I think of this expression probabilistically.Let's define a Random variable $$X$$,which counts the number of heads obtained when an unbiased Coin is thrown n times in a succession independently.So $$\mathbb{P}(X=k)=\binom{n}{k}(\frac{1}{2})^n$$.So if you multiply the LHS by $$(\frac{1}{2})^{n}$$ it becomes $$\mathbb{E}(X^{3})$$.And we know that $$\mathbb{E}(X^{3})=\frac{n^{2}(n+3)}{8}$$.Then you get the desired RHS.