# Chaitanya's Random Pages

## June 30, 2015

### The Pakistan heat wave of 2015

Filed under: climate and weather — ckrao @ 11:39 am

This month a heatwave has killed over 1500 people in Pakistan, most of them in Karachi. Here are the temperatures recorded at Karachi airport at that time: note that the average for this time of year is 28-35°C with high humidity. Rarely does the temperature reach 39.5°C three days in a row but here it did so six days in a row plus there seemed to be no relief at night.

 Date 16-Jun 17-Jun 18-Jun 19-Jun 20-Jun 21-Jun 22-Jun 23-Jun 24-Jun Min (°C) 30 29.3 29.5 31 31.6 33 33 33 30.5 Max (°C) 36 38.5 39.5 40.5 44.8 42.5 42.5 41.2 37

Most of the dead were homeless and it was also during the time of Ramadan where fasting is observed during daylight hours. This and the recent heatwave in India are two of the three most fatal on the Indian subcontinent in recent times.

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

Blog at WordPress.com.