Possible combinations of binary digits

Question

Why do we say 2 raised to a "n" ,where n is the number of digits = the possible combinations for that binary number

For example:

(00000000)2 Has 2 raised to 8 = 256

Why?

Answer 1

The maximum value of a binary number with $n$ digits is $$\overbrace{1111\dots1111_2}^{n\text{ ones}}=\overbrace{10000\dots0000_2}^{n\text{ zeroes}}-1=2^n-1$$ Hence as the minimum value is $0$ and maximum value is $2^n-1$ there are $2^n$ possible combinations which each correspond to a single decimal value.

Another way to consider this is to write out each digit seperately. The first digit can be $0$ or $1$ hence there are two possible choices, the second digit can be $0$ or $1$ hence there are two choices etc. As you make $n$ choices for the $n$ digits in the number, the total number of combinations is the same as the number of possible choices which is $$\overbrace{2\times2\times\dots\times2\times2}^{n\text{ twos}}=2^n$$

Answer 2

If you write numbers in ordinary base $10$ there are $10$ digits, so $10$ one digit numbers $0, 1, \dots, 9$. Then you have to start a "tens column". There are $100 = 10^2$ two digit numbers, starting with $00$ and ending with $99$. In general, there are $10^n$ $n$-digit numbers.

Now think through what happens in base $2$ when the only digits are $0$ and $1$.

Answer 3

An $n$ bit representation, written [0100...1] or so for $n$ values that could be either $0$ or $1$, is secretly a function: it is a function which takes an index $k$ where $1 \le k \le n$ and maps it to the set $\{0,1\}$. Indeed in some ways of defining the integers, $0$ is secretly represented as the empty set $\emptyset = \{\}$ and every other counting number is represented as the set of all the numbers which came before it, so $1 = \{\emptyset\} = \{0\}$ and $2 = \{\emptyset, \{\emptyset\}\} = \{0, 1\}$ and so forth, and so an $n$-bit representation is literally a function $n \to 2$.

For finite sets $A\to B$ the number of possible functions is related to the cardinalities $|A|$, $|B|$ by $$|A\to B| = |B|^{|A|}.$$Indeed this is so prevalent that sometimes we just write these functions not as $A\to B$ but as $B^A.$ Indeed especially $2^S$ is seen very, very often: it is the set of all subsets of $S$, sometimes known as the power set of $S$. (A function $S \to \{0,1\}$ can be understood as precisely that subset of $S$ which it maps to $1$.) But you can also see for example $\mathbb N^2 = \mathbb N \times \mathbb N$, the set of pairs of natural numbers, as functions $\{0,1\}\to\mathbb N$ (input $0$ to get the left element of the pair, input $1$ to get the right element).

This algebra can also be very helpful. For example it is known that $\mathbb N$ describes one infinity of points, a “countable” infinity, but that the powerset $2^{\mathbb N}$ is a fundamentally larger “uncountable” infinity. One might ask if $\mathbb N^\mathbb N$ is an even larger infinity, but through some formally-invalid manipulation, we have some idea that, $$\mathbb N^\mathbb N \approx 2^{\mathbb N~\log \mathbb N}\ll 2^{\mathbb N^2} $$but there is a well-known bijection where $\mathbb N^2$ has the same size as $\mathbb N$ and so this hints at a proof strategy, start from functions $\mathbb N\times\mathbb N \to \{0,1\}$ and show that those encode functions $\mathbb N\to\mathbb N$. And then by currying the function you really just need to show that a natural number can be encoded as a function $\mathbb N \to \{0,1\}$ , which there are many ways to do (binary expansion with the least-significant place first being the most obvious, but you can also just do computationally-wasteful ones like "$f_n$ is the function which maps $n$ to $1$ and every other counting number to $0$."

So, uh, it's not just that it has the size $2^n,$ in one way of denoting this set it is the set $2^n.$