2
$\begingroup$

I am looking to find a proof by double counting.

Logically concerning the left hand side I was thinking about the number of all subsets of a n-set.

On the right hand side following the same logic I see that with the same logic this will translate to summing up the number of subsets of all k-sets for k=0 to n-1 and then adding one more set.

This seems a bit counterintuitive as there are a lot of sets that will be counted double.

I looked at the building up of the subsets from k to k+1 and tried finding a recurrence relation.

I noticed that in fact the number of subsets of a n-set is equal to the amount of the subsets in n=0 to n-1 added together plus 1. But I cant see why this is true.

It makes more sense to me that $2^n$ is equal to the sum of all subsets of length $k=0$ to $n-1$ and then adding the set itself so plus 1 and thus having $2^n=1+\sum_{k=0}^{n-1}\binom{n}{k}$.

I am quite sure we could get from those binomial coefficients to the $2^k$ that we want to find. But this would not be a double counting proof anymore.

Maybe I need to look at the problem in another angle?

$\endgroup$
1
$\begingroup$

Let's count the number of subsets of $\{0,1,2,...,n\}$.

On the LHS, it's $2^n$, because each element either is or is not a member of a subset, and making that choice for each element leads to a different subset.

On the RHS, we count the subsets based on their largest element. The empty set is an outlier, so we count that separately. Beyond that, there are $2^0$ subsets whose greatest element is $1$ (just $\{1\}$), $2^1$ subsets whose greatest element is $2$ (both $\{2\}$ and $\{1,2\}$), and generally $2^k$ subsets whose greatest element is $k+1$.

Therefore, $$2^n=1+\sum_{k=0}^{n-1}2^k$$

$\endgroup$
  • $\begingroup$ Thanks for this clear solution, this makes sense. $\endgroup$ – Piri Sep 30 '19 at 22:22
1
$\begingroup$

Hint: count the number of subsets of $\{1,2,...,n\}$. First consider that in your choice for every subset, you can choose whether or not ($2$ choices) to include each of the $n$ elements, which gives you $2^n$. Then consider fixing the size of the subset, say $k$, and for each $k$ see how many subsets you can choose, and then sum up as $k$ runs through $1,2,...,n$.

$\endgroup$
1
$\begingroup$

Let's count all non-empty subsets of $\{1,2,\ldots,n\}$ twice.

We get $2^n - 1$ via the standard argument that we can either include element $i$ in a subset or not (giving is $2^n$ options, by $n$ independent choices) and substracting the empty set from it (the $-1$).

Let (for $k=1,\ldots,n$) the collection $A_k$ be all subsets $A$ of $\{1,2,\ldots,n\}$ with $\max(A) = k$. For different $k$ these sets are disjoint: a non-empty finite set has a unique maximum; it cannot be both $i$ and $j$ where $i \neq j$, and every non-empty set has a maximum in $\{1,\ldots,n\}$ so these form a partition.

And $|A_k|= 2^{k-1}$, because to form a set in $A_k$ we put $k$ (the max) in $A$ and then take any subset of $\{1,\ldots,k-1\}$ (empty for $k=1$, but there are always $2^{k-1}$ subsets of it) and add it to $A$, and all $A \in A_k$ can be made that way, uniquely.

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

by a reindexing in the last sum. Now pull the 1 to the other side.

Alternatively add the empty set as a singleton in the partition of all subsets of $\{1,\ldots,n\}$ to get the formula directly.

$\endgroup$
  • $\begingroup$ Thanks for this solution, its the same as the one from Matthew Daly just a bit more formal. $\endgroup$ – Piri Sep 30 '19 at 22:24
  • 1
    $\begingroup$ @Piri You're welcome. I've always had to write combinatorial proofs this way (partitioning formally etc.). It's good training. $\endgroup$ – Henno Brandsma Sep 30 '19 at 22:30
1
$\begingroup$

Consider the set of binary sequences that are not the zero sequence $(x_1,\dotsc, x_n)$ of length $n$. There are $2^n-1$ such binary sequences. Now partition this set into sets $A_k$ based on the position $k$ that the first $1$ occurs. Then $|A_k|=2^{n-k}$ for $k=1,\dotsc, n$ from which the result follows.

$\endgroup$

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.