Is there a combinatorial proof of the following identity:
$$\binom{n+1}{2} + 2 \left ( \binom{2}{2} + \binom{3}{2} + \dots + \binom{n}{2} \right ) = 1^2+2^2+\dots+n^2.$$
Note: using algebraic manipulations and tools such as Pascal's identity the left hand side can be easily shown to be equal to $\frac{n(n+1)(2n+1)}{6}$ and by induction the right hand side can also be shown to be equal to $\frac{n(n+1)(2n+1)}{6},$ but I am looking for a combinatorial proof, something like a counting process which gives the LHS when counted in one way and the RHS when counted in another way.
Best Answer
Imagine we have $n+1$ members of an organization and they are all assigned a unique number corresponding to their skill level from $1$ to $n+1$.
Suppose we have two distinct jobs we wish to have completed and we want someone to supervise these jobs as well. The supervisor will be too busy watching to perform either of the jobs themselves, but we don't mind if it was one person performing both of the two jobs or if it were two people performing one of the jobs each. The supervisor must have a higher skill level than the person(s) performing the jobs.
On the right hand side, we can break into cases based on who the supervisor was. We then pick who does the first task, having chosen from those people less skilled than the supervisor. We then pick who does the second task remembering that it could have been the same person. This leads to the count as having been $1^2+2^2+3^2+\dots+n^2$
On the left hand side, we first break into cases based on whether it was only one person performing both jobs, or whether it was two people. If it was one person performing both jobs, just pick two people from the $n+1$... the more skilled person will act as the supervisor and the less skilled will perform both jobs. In the second case, if it was two different people performing the jobs, then break into cases further based on who the supervisor was. Then pick the two distinct people in sequence who will perform the jobs (equivalently pick the two people simultaneously and then assign the jobs after the fact, the difference between $n(n-1)$ and $\binom{n}{2}\cdot 2$). This leads to the count as having been $\binom{n+1}{2}+2\left(\binom{2}{2}+\binom{3}{2}+\binom{4}{2}+\dots+\binom{n}{2}\right)$