Why is $2^b-1=2^{b-1}+2^{b-2}+...+1$? Can I get an intuitive explanation why the formula in the title holds?
I know that it works but I am not sure why
$2^b-1=2^{b-1}+2^{b-2}+...+1$
 A: Consider the number $N=2^{b-1}+2^{b-2}+\dots+2^2+2^1+2^0$. Now let's look at $N+1$:
$$N+1 = 2^{b-1}+2^{b-2}+\dots+2^2+2^1+2^0+2^0\\
=2^{b-1}+2^{b-2}+\dots+2^2+2^1+2^1\\
=2^{b-1}+2^{b-2}+\dots+2^2+2^2\\
\vdots\\
=2^{b-1}+2^{b-2}+2^{b-2}\\
=2^{b-1}+2^{b-1}\\
=2^b$$
(since $2^k+2^k=2^{k+1}$ for any $k$), so $N=2^b-1$.
A: Consider the binary representation and it is clear.
$$111\cdots 1_2 + 1_2 = 1000\cdots 0_2$$
so
$$1000\cdots 0_2 - 1_2 = 111\cdots 1_2$$
But the LHS is $2^b-1$ and the RHS is  $2^0 +2^1 +\cdots + 2^{b-1}$.
It's just the binary way of saying what in decimal is (for example) 
$$10000-1=9999$$
A: A pack of $2^b$ balls can be splitted in two packs of $2^{b-1}$. The second pack can be splitted in two packs of $2^{b-2}$, etc. You go on until you have two packs of one ball each.
A: Let
$$S = 2^{b-1} + 2^{b-2} + \ldots + 1.$$
Multiplying through by $2$, you get
$$2S = 2^b + 2^{b-1} + \ldots + 2.$$
Now here is my hint:

HINT What do you get (on the RHS) after subtracting the first expression for $S$ from the second expression for $2S$?

A: Consider a single-elimination tournament, a tennis tournament, say, with $2^{b}$ players. 
How many matches are played? Let us count in two ways.
It's $2^{b-1}$ matches in the first round, $2^{b-2}$ in the second round, $\dots$, $2$ semifinals and $1$ final.
Another way of counting is that each match has a loser, and each player loses exactly one match, except for the winner, that loses none. So it's $2^{b} - 1$ matches.
A: You can visualize it by looking this identity as identity of polynomials: 
$$
(1-x)(1+x)=1-x^2
$$
$$
(1-x)(1+x+x^2)=1-x^3
$$
and in general 
$$
(1-x)(1+x+x^2+x^3+\ldots+x^{n-1})=1-x^n
$$ Now on substituting $x=2$, we get the desired result. Hope it helps.
