mjhjmtu

Give a combinatorial proof of the following identity: $$binom3n3 =3binomn3 +6nbinomn2 +n^3.$$

I've been working on this proof for hours, however I'm not able to show LHS = RHS-
I completely understand binomial theorem and few combinatorial proofs but not able to succeed this one.
Help would be appreciated.

$$3nchoose3=3nchoose3+6nnchoose2+n^3$$$$frac12ncdot(3n-1)cdot(3n-2)=frac12ncdot(n-1)cdot(n-2)+3n^2cdot(n-1)+n^3$$Can you take it from here?

Arrange $3n$ balls into 3 rows and each row contains $n$ balls.

There are $binomn3$ ways to select $3$ balls from them. We can group the ways into $3$ categories:

1. Select one ball from each row. There are $n$ choices for each row, this contribute $n^3$ ways of pick the balls.




2. Select two balls from one row and one ball from another row. There are $3 times 2$ ways to select the rows. Since there are $binomn2$ ways to select two balls from a row and $n$ ways to select one balls from a row, this contribute $6 binomn2 n$ ways to pick the balls.




3. Select three balls from a single row. There are $3$ ways to select the row and $binomn3$ ways to select three balls from that particular row. This contributes $3binomn3$ ways.

These $3$ categories of choicing doesn't overlap and exhaust all possible ways to select three balls. As a result,

$$binom3n3 = n^3 + 6binomn2 n + 3binomn3$$

$2!=2, 3!=6$, so:

$$binom3n3=frac n2(3n-1)(3n-2)$$
$$3binomn3=frac n2(n-1)(n-2)$$
$$6nbinomn2=3n^2(n-1)$$

I used that $$fracx!(x-a)!=x^underlinex-a=prod_n=0^a-1(x-n)$$

See falling factorials

Brute force:

$27n^3 - 27n^2+ 6n = 27n^3 - 27n^2 + 6n$

$27n^3 - 9n^2 - 18n^2 + 6n = 3n^3 - 3n^2 - 6n^2 + 6n + 18n^3 - 18n^2 + 6n^3$

$(9n^2 - 3n)(3n - 2) = (3n^2 - 3n)(n - 2) + 18n^2(n-1) + 6n^3$

$3n(3n - 1)(3n - 2) = 3n(n - 1)(n - 2) + 3(6n)n(n-1) + 6n^3$

$3n(3n - 1)(3n - 2)/6 = 3n(n - 1)(n - 2)/6 + (6n)n(n-1)/2 + n^3$

$binom3n3 =3binomn3 +6nbinomn2 +n^3$

Notice that the LHS is:

$$frac3n times (3n-1) times (3n-2)3! = fracn times (3n-1) times (3n-2)2$$
$$to frac9n^3-9n^2+2n2$$

For the RHS:

$$3 times fracntimes(n-1)times(n-2)3! + 6n times fracntimes(n-1)2! + frac2n^32$$

$$Longrightarrow fracntimes(n-1)times(n-2)2 + frac6n^2 times(n-1)2 + frac2n^32$$

$$to frac9n^3-9n^2+2n2$$

Hence, RHS=LHS.