# combinatorial proof of summation

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$.

• This answer also provides a combinatorial interpretation. And here is another one. Sep 29 '14 at 12:36

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?

• 2^n minus the one case where all lights are off, 2^n-1. 2^(n-i),as the switches are specified whereas in the first it can be any one switch. Sep 29 '14 at 20:59
• @user2008730 $n-i+1$ switches are specified, not $i$ of them. Sep 29 '14 at 21:41

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$.

• Isn't this inductive proof? By "combinatorial proof" most people mean a proof that gives a combinatorial meaning to both sides of the identity. Your proof is perfectly valid, but it doesn't contain any combinatorics. Nov 9 '14 at 16:04
• @WillOrrick: I guess so. Nov 9 '14 at 17:02
• I see now that in the proof above the first paragraph refers to the RHS while the second to the LHS. Now it makes more sense. Nov 9 '14 at 18:01