0
$\begingroup$

Let $S_k$ be a set with $k$ elements. Then $S_k$ has $2^k$ subsets. So the formula $2^{n+1}-1 = \sum_{k=0}^n 2^k$ can be translated to $$\text{number of *nonempty* subsets of $S_{n+1}$} = \sum_{k=0}^n\text{number of subsets of $S_{k}$}.$$ Is there a combinatorial way of seeing that this formula must hold?

(I'm not looking for non-combinatorial proofs like $(2-1)\sum_{k=0}^n 2^k = 2^{n+1}-1$)

$\endgroup$
6
  • $\begingroup$ Hint:\begin{align}&\text{number of non-zero $(n+1)$-digit binary words}\\=&\sum_{k=1}^{n+1}\text{number of k-digit binary words with leading $1$}\end{align} $\endgroup$
    – Peter Foreman
    Commented May 27, 2020 at 11:29
  • 1
    $\begingroup$ Does this answer your question? The idea behind the sum of powers of 2 - combinatorial proof by Foobaz John. $\endgroup$
    – Dietrich Burde
    Commented May 27, 2020 at 11:31
  • $\begingroup$ @DietrichBurde yes, I think so. Thanks! $\endgroup$
    – Epiousios
    Commented May 27, 2020 at 11:34
  • 1
    $\begingroup$ I've posted a new answer on the old question, giving a proof technique it looks like they missed until now, despite its being well-known. $\endgroup$
    – J.G.
    Commented May 27, 2020 at 12:01
  • 1
    $\begingroup$ Please see my combinatorial proof here. $\endgroup$
    – RobPratt
    Commented May 27, 2020 at 16:35

0

Reset to default