Since I wasted 2 hours learning double counting I decided to make a problem that has to require double counting


Prove that \(n*\binom{n}{n}+(n-1) \binom{n}{n-1}+…+0 \binom{n}{0}=n2^n-1\)


You can use the binomial theroem to prove this when your done with the double counting.angel

 Jul 9, 2022

Very interesting problem, indeed. I saw this problem on a textbook and the solution was very intriguing. 

Suppose we flip n choose k with n choose n - k...

This tuns the expression into:


\(n*\binom{n}{0}+(n-1) \binom{n}{1}+…+0 \binom{n}{n}\)

We can combine the (n k) terms with the (n n-k) terms to get n as the coefficient and multiply it by two because by combining, we halved the amount of terms. 


This gives us:
\(n*\binom{n}{0}+(n) \binom{n}{1}+…+n \binom{n}{n}\)

Note that if we factor out n on the left side, we get 2^n as the inside term(Make sure you know why) and n. But because we have multiplied the expression by two earlier, we have to divide it by two to get its true value. This gives us:


So @BigBrain, I think there was a slight error. 

 Jul 9, 2022

Yes my bad double counting is about different ways to count a set. laugh

BigBrain  Jul 10, 2022

14 Online Users