Dissecting a combinatorial proof

Question

I get a little bit of how combinatorics proofs work, but I am trying to understand a better way of dissecting them. Essentially, I have problems where I'm given a LHS and a RHS and I have to explain it with a proof/argument, usually a lot of examples talk about students, committees, etc.

For example, if we consider the following:

$\sum_{k=2}^{n} k(k-1)\begin{pmatrix}n\\ k \end{pmatrix}5^{k} = 25n(n-1)6^{n-2}$

What does every expression tell me? A lot of problems I see have some sort of number to the power of (n-1) or (n-2) and I think that would mean that of whatever people we chose for the LHS, there is $6^{n-2}$ people left for the RHS for example. I could also say that because of the (n-1), we have to have a minimum of 2 people on the RHS. The rest of the problem I do not fully understand. I am trying to see how I can turn this math into a argumental proof.

For the RHS, I would probably say something along the lines of "There will a lucky person chosen for a gift out of n people. At least 2 people will get a gift. One winner is selected followed by another and they have 5 gifts to select from." etc. That's as far as I can figure out. If I could fully understand this one, that would probably really help me out understanding many others like this. I'm not sure if everything I put down is correct but it's with my best attempt.

Answer 1

Hint

Here is a possible story for the LHS:

• Choose some number $k$ betweeen $2$ and $n$.

• There is then a $\binom{n}k$ term, suggesing there are $n$ distinct objects, and we select $k$ of them.

• There is then a $5^k$ term. So there we are making $k$ five-way choices. We have already selected $k$ objects, perhaps we are assigning each of them one of five colors.

• There is now a factor of $k$, so we are making a $k$-way choice. We have singled out $k$ objects, perhaps we are selecting one of them.

• Finally, we make a $(k-1)$-way choice, suggesting we are selecting another one of the special objects, different from the last selection.

At the end, we have $n$ objects, combing in $6$ varieties; either uncolored, or colored in one of $5$ colors, and where two of the colored objects are singled out. You now just need to figure out how this is described by the RHS.

Answer 2

You are nearly there... There are $n$ people some of whom will recieve one of $5$ possible prizes (but some will recieve nothing). Also one person will definitely recieve a prize and the title of chair person and a different person will also definitely get a prize and they title of assistant chair person. ... this gives the RHS.

Another way to figure is ... $k$ people will recieve prizes ($\binom{n}{k} 5^k $ ways.) Now choose the chair person from this set of $k$ people ($k$ ways) and the assistant chair person ($k-1$ ways.) Now observe that $k$ can take any value from $2$ upto $n$ & we have the LHS.