# Chaitanya's Random Pages

## June 22, 2015

### Places we see powers of 2

Filed under: mathematics — ckrao @ 11:44 am

Here are some obvious and less obvious places where we encounter the sequence $f(n) = 1,2,4,8,16,...$. Most of these come from the corresponding OEIS page.

• as a solution to the recurrence $f(n+1) = 2f(n), f(0) = 1$.
• the number of subsets of a n-element set: To each element there are two choices – to include it or not include it in the subset. Hence there are $2\times 2\times \ldots \times 2 = 2^n$ subsets.
• the sum of the numbers in the n’th row of Pascal’s triangle This is a consequence of the binomial theorem applied to $(1+1)^n = \sum_{i=0}^n \binom{n}{i}$.
• the sum of the coefficients of $(x+1)^n$, which is the sum of binomial coefficients
• the number of even or odd-sized subsets of an (n+1)-element set, i.e. $\sum_{i=0}^{\lfloor{(n+1)/2}\rfloor} \binom{n+1}{2i} = \sum_{i=0}^{\lfloor{n/2}\rfloor} \binom{n+1}{2i+1} = 2^n$, a consequence of the binomial theorem $(1-1)^n = \sum_{i=0}^n (-1)^i \binom{n}{i}$.
• each term in the sequence is the smallest natural number that is not the sum of any number of distinct earlier terms, an example of a sum-free sequence
• the sequence forms the set of every natural number that is not the sum of 2 or more consecutive positive integers: Such a sum has the form $a + (a+1) + \ldots + (a+ k) = (2a + k)(k+1)/2$. If this were a power of 2 then $(2a+k)$ and $(k+1)$ must both be powers of 2 greater than or equal to 2. But their difference $2a-1$ is odd, which is impossible for the difference of even powers of 2. Conversely if a natural number is not a power of two it is of the form $2^m d$ where $d$ is an odd number at least 3. Then $2^m d$ may be written as the sum of either $d$ consecutive positive integers with middle (mean) term $2^m$ (if $(d+1)/2 \leq 2^m$) or $2^{m+1}$ consecutive positive integers with mean $d/2$ (if $2^m < d/2$). For example, $48 = 2^4\times 3$ and $48 = 15 + 16 + 17$ while $44 = 2^2\times 11$ and $44 = 2+3+4+5+6+7+8+9$.
• the number of ordered partitions of $n+1$ is $2^n$: for example, the eight ordered partitions of 4 are: 1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2, 3+1, 1+3, 4 To see why this result is true, imagine $n+1$ items in a row. Imagine separating them with dividers so that the number of items between each divider gives us the ordered partition. For example with 4 items we may place a divider between the third and fourth item to give the partition 3+1. We have $n$ possible locations for dividers (between any adjacent items) and each location has a choice of being assigned to a divider or not. This leads to $2^n$ possible partitions. Alternatively, an ordered partition of $n+2$ may be derived inductively from an ordered partition of $n+1 = a_1 + \ldots + a_k$ by either forming $n+2 = 1 + a_1 + \ldots + a_k$ or $n+2 = (a_1+1) + a_2 + \ldots + a_k$. Also any ordered partition of $n+2$ has one of these forms as we may form from it an ordered partition of $n+1$ by either subtracting 1 from the first element of the partition (if it is greater than 1) or deleting the first element if it is 1. Hence the number of partitions doubles as $n+1$ is increased by 1 and for $n = 1$ we have the single partition.
• the number of permutations of ${1,2,...,n+1}$ with exactly one local maximum: for example, for $n=3$ we have the permutations 1234, 1243, 1342, 2341, 1432, 2431, 3421, 4321. Here we have the highest element $n+1$ somewhere and there are $2^n$ possible subsets of ${1,2,...,n}$ that we may choose to precede it. These elements must be in ascending order, while the elements after $n+1$ are in descending order to ensure exactly one local maximum at $n+1$. Hence the order of terms is determined once the subset is chosen and we have $2^n$ permutations.
• the number of permutations of $n+1$ elements where no element is more than one position to the right of its original place: for example, for $n=3$ the allowed permutations are 1234, 1243, 1324, 1423, 2134, 2143, 3124, 4123. This can be seen inductively: if $a_1a_2\ldots a_{n+1}$ is a valid permutation of n+1 elements, then $1(1+a_1)(1+a_2)\ldots (1+a_{n+1})$ and $(1+a_1)1(1+a_2)\ldots (1+a_{n+1})$ are valid permuations of n+2 elements. Also any valid (n+2) element permutation is of this form as it may be reduced to a valid (n+1) element permutation by deleting the 1 (which must occur in either the first or second position) and subtracting 1 from every other element. This describes a one to two mapping between valid permutations of n+1 and n+2 elements. Finally for 1 element there is $1 = 2^0$ allowed permutation, so the result follows by induction.