0

Prove the following binomial identity using a counting proof:

$$\sum\limits_{r=0}^n (r+1)\cdot {n \choose r} = (n+2)\cdot 2^{n-1}$$

I expanded the right side to get: $2^n + n2^{n-1}$, because I think that will be easier to count but have not been able to actually get any farther. Thank you.

RobPratt
  • 45,619
walterman
  • 23
  • 5
  • Do you mean $(n+2)2^{n-1}$ or $(n+2)2^n-1$? (You'll find it very helpful to begin learning to use TeX. Put dollar signs around your math expressions, and use curly brackets, { and }, to group things that go together. People will help fix things that don't look right.) – Barry Cipra Sep 27 '20 at 23:22
  • the first one, sorry – walterman Sep 27 '20 at 23:26
  • 3
    Hint: $r{n\choose r}$ counts the number of chaired committees of size $r$, chosen from an assembly of size $n$, while $n\choose r$ counts the number of unchaired committees of size $r$. – Barry Cipra Sep 27 '20 at 23:35
  • You should accept one of the answers or say what else do you need. – markvs Sep 28 '20 at 20:21
  • I did, sorry i'm new to the website – walterman Sep 28 '20 at 20:27

3 Answers3

0

You started correctly. Then your equality is equivalent to $\sum_0^n {n\choose r}+\sum_0^n r {n\choose r}=2^n+n2^{n-1}$. But by the binomial formula $\sum_0^n {n\choose r}=2^n$. So your equality is equivalent to $\sum_0^n r {n\choose r}=n2^{n-1}$. This can be proved by induction on $n$ or by counting chaired committees as in @BarryCipra's comment. This has been done here already.

markvs
  • 19,653
0

Expand the lefthand side as well:

$$\sum_{r=0}^n(r+1)\binom{n}r=\sum_{r=0}^nr\binom{n}r+\sum_{r=0}^n\binom{n}r\,.$$

The second summation gives the number of ways to choose a team of any size from a pool of $n$ players; clearly this is just the number of subsets of the pool, which is $2^n$. The first summation gives the number of ways to choose a team of any size $r$ and then appoint one of those $r$ players captain; that can just as well be done by choosing the captain and then choosing $r-1$ players from the remaining $n-1$ to fill out the team, something that can be done in $n\binom{n-1}{r-1}$ ways. Thus,

$$\sum_{r=0}^nr\binom{n}r=n\sum_{r=0}^n\binom{n-1}{r-1}=n\sum_{r=0}^{n-1}\binom{n-1}{r-1}\,,$$

which is just $n$ times the number of ways to pick a subset of the remaining $n-1$ players, or $n2^{n-1}$. And this is exactly the righthand side that you have.

(By the way, the identity $r\binom{n}r=n\binom{n-1}{r-1}$ is often useful and is worth knowing.)

Brian M. Scott
  • 616,228
0

If only counting is allowed, consider the number of all committees, chaired and not.

We can count them in two ways. First choose number $r=0,...,n$ and a subset with $r$ elements from a set of $n$ elements. Then we choose a chair of that committee or no chair at all. The total number of choices is the LHS of your equality.

We can compute it in a different way. First count the number of all chairless committees. These are all $2^n$ subsets of the $n$-element set. Then we count the chaired committees by first choosing a chair ($n$ choices) and then choosing a subset of the set of members witbout the chosen chair ($2^{n-1}$ choices). Altogether the number is equal to the RHS of your equality.

So LHS=RHS.

markvs
  • 19,653