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.
Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: