0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This answer also provides a combinatorial interpretation. And here is another one. $\endgroup$ Sep 29 '14 at 12:36
7
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – miniparser
    Sep 29 '14 at 20:59
  • $\begingroup$ @user2008730 $n-i+1$ switches are specified, not $i$ of them. $\endgroup$
    – Slade
    Sep 29 '14 at 21:41
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Nov 9 '14 at 16:04
  • $\begingroup$ @WillOrrick: I guess so. $\endgroup$
    – miniparser
    Nov 9 '14 at 17:02
  • $\begingroup$ 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. $\endgroup$
    – miniparser
    Nov 9 '14 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.