I was hoping someone could help me come up with a combinatorial proof, one with an easy to understand 'story' for $\sum_{k=0}^{n-1} 2^{k} = 2^n - 1$. For instance I understand that $2^n$ is the number of possibilities when creating subsets of size $n$. For example, if you're given a choice of any topping on a pizza, and you can only have said topping once (decide to include or exclude) then you have $2^n$ choices. But I'm not sure how the $-1 $ would be incorporated, or why the LHS would be $1+2+4+8+...+2^{n-1}$
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Well, If you can have $m$ toppings and you are not allowed to have a plain pizza then... If you can have $K_m$ types with $m$ toppings, and then someone gives you a new $m+1$ topping how many extra pizzas can you make. All your new pizzas have the new topping and they may or may not have any of the old $m$ toppings. So there are $2^m$ new pizza types. So if $K_m$ is the number of pizzas with $m$ toppings, then $K_{m+1} = K_{m} + 2^m$ is the number with $m+1$ toppings. But $K_m$ mus be $2^{m-1} + K_{m-1}$ and so on. And $K_0$ is $0$ as we aren't allowed to not have toppings so ....$ $\endgroup$– fleabloodCommented Sep 22, 2019 at 20:26
-
$\begingroup$ $K_{m+1} = 2^m +2^{m-1} + .... + 2^0$. But we can figure logically that if we have $m+1$ toppings there are $2^{m+1}$ pizzas but if we subtract the type with no toppings. we have $K_{m+1} = 2^{m+1} -1 = 2^m + 2^{m-1} + .... + 2^0$. $\endgroup$– fleabloodCommented Sep 22, 2019 at 20:28
-
$\begingroup$ The $-1$ is an offset. You have a the sum $2^m + 2^{m-1} + .... + 8 + 4 + 2 + 1$. If you add $1$ to that you.... set off an avalanch. The $1$ adds to the one and you get $2$. That add to the $2$ and you get $4$. That $4$ adds to the $4$ and you get $8$. And so on.... or if you have $2^m$ you can split it in half. And get two $2^{m-1}$. Yo split that in half, and take one of the resulting $2^{m-1}$s and split it in half and so on.... eventually you get a $4$ and split it to two $2$s and you split the $2$ into two $1$ and you take a $1$ and... throw it away. $\endgroup$– fleabloodCommented Sep 22, 2019 at 21:49
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
Both sides count the number of games in a single-elimination tournament with $2^n$ teams. The left side counts the number of games by round, and the right side is obtained by noting that all teams but the winner lose one game each.
-
$\begingroup$ that makes a lot of sense actually, thank you! $\endgroup$– clovisCommented Sep 22, 2019 at 22:48
$\begingroup$
$\endgroup$
0
How many strings of $0$s and $1$s of length $n$ are there which have at least one $1$?
There are $2^n$ strings total, except we want to omit the string of all $0$'s, so $2^n-1$.
Consider the location of the rightmost $1$, at spot $k$, for some $k\in \{1,2,\dots,n\}$. Given the rightmost $1$ is at spot $k$, the first $k-1$ spaces can be chosen in $2^{k-1}$ ways, while the rest of the string is then forced (since there are only $0$'s to the right of the rightmost $1$). Summing over $k$, the number of strings is $\sum_{k=1}^n2^{k-1}=\sum_{k=0}^{n-1}2^{k}$.
Equating the two answers, you get $2^n-1=\sum_{k=0}^{n-1}2^k$.
Don't get too caught up with trying to come up with a "story" involving pizza or children or candy or committees; this can obscure the simplicity of the solution.
answered Sep 22, 2019 at 22:25
$\begingroup$
$\endgroup$
0
Imagine you are not allowed to have a pizza with no toppings.
Then if you have $m$ possible toppings you are allowed to have $2^m -1$ toppings. (For any type of topping you can or can not include it. That is $2^m$ choices. But that includes excluding every topping and having a pizza with no toppings. That's not allowed so you are allowed $2^m -1$ types of pizzas.)
Now what if you choice was $0$ toppings how many pizzas can you have? Well, zero.
And if you had one topping how many? Well, $1$.
Okay, now let's say I gave you a new topping. How many more new types of pizzas could you add to the number you could already make?
Well, every new type will have the new topping. And of the $m$ old toppings I can either include it or not. So that is $2^m$ new types.
So if I get a second topping I can make $2^1$ new pizzas and now make $1+2$ types of pizzas.
And if I get a third topping I can make $2^2$ new pizzas and now make $1+ 2 + 4$ types of pizzas.
....
And if I get an $m$th toppin I can make $2^{m-1}$ new types of pizzas and now can make $1+2+4+ .... + 2^{m-1}$.
SO by those two different calculations I figure if I have $m$ toppings I can have $2^m-1$ different types or $1 + 2+ 4+ ..... + 2^{m-1}$ different types.
answered Sep 22, 2019 at 20:39