+50 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.
+289 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:
\(n2^{n-1}\)
So @BigBrain, I think there was a slight error.
