cool_induction_proof

Created on May 24, 2025

2025

Recently I have been working through Introduction to Proof theory by Cummings and I might have found my new favorite induction proof. The proof is somewhat simple looking though it can be very fun to figure out by hand. I will state the problem here and then give the solution I came up with but I urge you to try and solve it before looking at my solution.

\[\begin{equation} \label{prop} |A| = n \implies |P(A)| = 2^n \end{equation}\]

Direct Proof

What this questions is asking is that if you take the magnitude of a set $A$, that is n. Will the magnitude of the power set of $A$ always be $2^n$? The strange thing I found here was that for a computer scientist there exists a somewhat obvious direct proof using binary. In particular the way a power set is constructed is every possible combination of the original set form the sub-sets of the power set. If we were to represent each element of the set $A$ as a single binary bit we can do something like this.

\[\begin{equation} \begin{split} A = {1,2,3,4,...,n} \\ B = {1_1,1_2,1_3,1_4,...,1_n} \end{split} \end{equation}\]

Where $B$ represents the possible binary bits that mirror the elements of set $A$. Now the binary representation will show us how my possible sets can be made.

\[\begin{equation} \label{bin} \begin{split} A = {1,2,3,4,...,n} \\ B = {1_1,1_2,1_3,1_4,...,1_n} \\ C = {2^0,2^1,2^2,2^3,...,2^{n-1}} \end{split} \end{equation}\]

Here the trick is that we know if all bits are on then the possible sets are $ \sum^k_{k=0} 2^k $. We also know that if all bits are on and get added together then it is equal to $ 2^n - 1 $. That said when constructing the power set the empty set is taken into account; thus $2^n - 1 + 1$. This direct proof is already cool (even though it is not rigorous in the least). So how does it get more interesting?

Inductive proof

First of all lets examine Pascals theory of combinations which is an awesome law, Eq. \eqref{pascals}.

\[\begin{equation} \label{pascals} \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \end{equation}\]

This law implies that given a combination $\binom{n}{k}$ we can construct it from the combination of lesser $n$. I did not know this (or at least remember it), thus solving this inductive proof was somewhat of an Easter egg hunt.

However given Eq. \eqref{pascals} we can begin the inductive proof.

\[\begin{equation} \label{hyp} \begin{split} \text{Hypothesis} \\ n \in \mathbb{N} \\ 1 + \sum^n_{k=1} \binom{n}{k} 2^n \end{split} \end{equation}\]

This is playing on the same kind of idea from Eq \eqref{bin}. We know that the power set is constructed using all combinations of all magnitudes from the set $A$. Thus we take the summation of all combinations.

\[\begin{equation} \label{base} \begin{split} \text{Base Case} \\ n = 1 \\ 1 + \binom{1}{1} \triangleq 2^1 \end{split} \end{equation}\]

In the base case Eq \eqref{base} we see that it works for a single possible value of $n$.

\[\begin{equation} \label{step} \begin{split} 1 + \sum^{n+1}_{k=1} \binom{n+1}{k} 2^{n+1} \\ \text{Given Eq. \eqref{pascals}} \\ 1 + \sum^{n}_{k=1} ( \binom{n}{k-1} + \binom{n}{k} ) = 2^n * 2 \\ \end{split} \end{equation}\]

Here the math becomes somewhat confusing, The trick I pulled with pascals identity (Eq \eqref{pascals}) can be done for $2^{n-1}, 2^{n-2}, …$. With this in mind the next equation should make more sense.

\[\begin{equation} \label{step_final} \begin{split} 1 + \sum^{n}_{k=1} ( \binom{n}{k-1} + \binom{n}{k} ) = 2^n * 2 \\ (\sum^{n}_{k=1} \binom{n}{k-1}) + 1 + \sum^{n}_{k=1} \binom{n}{k} = \\ (\sum^{n}_{k=1} \binom{n}{k-1}) + 2^n = 2^n * 2 \\ \{1 + \dots + 2^{n-3} + 2^{n-2} + 2^{n-1}\} + 2^n = 2^n * 2 \\ 2^n + 2^n \triangleq 2^n * 2 \end{split} \end{equation}\]

Using the law that any power of two $2^n$ is equal to the summation of all powers of two up to $2^{n-1}$ we can see that the algebra works out. $\therefore$ the proposition is proved via induction; completing my new favorite induction proof.

Nomanclature

  • $P$: This represents the power set function. $P: A \rightarrow B$
  • $ || $: Any set surrounded by these symbols denotes the magnitude of the given set, thus $|A|$ denotes the magnitude of A (or length for my CS people).
  • $ \implies $: denotes the logic implies.
  • $ \binom{n}{k} $: denotes combination operation.
  • $ \sum^{n}_{k=0} $: denotes the sum of all values from $k=0$ to $k=n$.