I'm trying to come up with a combinatorial proof for the given expression:
$\sum_{k=0}^{n-1} 2^k = 2^n - 1$
I know the algebraic method to prove the given expression, where I simply substitute the values into the expression for the sum of a GP with n terms. I was trying to come up with a combinatorial proof for the same but couldn't solve it. I considered the RHS as the total number of bit strings of length n except the string with all 0's. However, I can't see how to count the same on LHS.
Any help is appreciated.