combinatorial proof of summation

Question

Prove $\sum_{i=1}^n2^{i-1}=\sum_{i=0}^{n-1}2^i=2^n-1$ combinatorially.

This is easy to prove inductively. I know that $\sum_{i=0}^n{n\choose i}=2^n$ so maybe change $\sum_{i=0}^{n-1}2^i$ to $\sum_{i=0}^{n-1}\sum_{j=0}^i{i\choose j}$. I also know that $2^n-1$ is the number of proper subsets in a set of size $n$.

Answer 1

Suppose I have $n$ light switches, numbered $1$ through $n$. I'd like at least one light on, but other than that I can select any configuration. How many configurations are there?

Now, for some $i$ with $1\leq i\leq n$, how many configurations are there with the property that switch $i$ is on, but all switches to its right are off?

Answer 2

I have my own combinatorial proof for this.

$\sum_{i=0}^{n-1}2^i=2^n-1$

Interpreted as $2^0+2^1+2^2+...+2^{n-1}$

Each increase of $n\ge 1$ by $1$ LHS increases the total by the current total plus one, making the total $(2^{n-1}-1)+2^{n-1}=2(2^{n-1})-1=2^n-1$.