## Tuesday, March 14, 2017

### Pi Day 2017

Happy Pi day (and a snowy one in the Northeastern US)! One of the early childhood mathematical memories I had was learning that π can be approximated by 22/7 and accurate up to 2 decimal places, a fact that was known since antiquity. In particular, Archimedes gave the first proof that 22/7 is strictly larger than π. The fifth century Chinese mathematician and astronomer Zu Chongzhi gave the approximation 355/113 that is accurate up to 6 decimal places. Today, sophisticated algorithms using Ramanujan's formula and its variants can compute trillions of digits of π.

## Thursday, March 9, 2017

### Binomial coefficients

When studying binomial coefficients and how they form Pascal's Triangle, we learn that they are the coefficients of $(x+y)^n$, i.e.
$$(x+y)^n = \sum_{k=0}^n \left(\begin{array}{c}n\\k\end{array}\right)x^ky^{n-k}$$
Replacing $y$ with $-y$ we get:
$$(x-y)^n = \sum_{k=0}^n -1^k\left(\begin{array}{c}n\\k\end{array}\right)x^{n-k}y^{k}$$

For example, the coefficients of $(x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4$ are 1,4,6,4,1 which form the 5th row of Pascal's triangle.

What happens if the coefficients of the polynomial are repeated binomial coefficients such as 1,1,4,4,6,6,4,4,1,1? What is $$\sum_{k=0}^{2n+1} \left(\begin{array}{c}n\\\lfloor k/2\rfloor\end{array}\right)x^ky^{n-k}?$$

It is easy to show that this is equal to $y(x^2+y^2)^n + x(x^2+y^2)^n = (x+y)(x^2+y^2)^n$.

What about repeating coefficients with sign changes such as 1,1,-4,-4,6,6,-4,-4,1,1?
The same argument shows that

$$\sum_{k=0}^{2n+1} -1^{\lfloor k/2\rfloor}\left(\begin{array}{c}n\\\lfloor k/2\rfloor\end{array}\right)x^{n-k}y^{k}$$

is equal to $y(x^2-y^2)^n + x(x^2-y^2)^n = (x+y)(x^2-y^2)^n$ which can be further simplified as $(x+y)^{n+1}(x-y)^n$.

If we now change the sign of every other coefficient as well, i.e. 1,-1,-4,4,6,-6,-4,4,1, -1,
we get

$$\sum_{k=0}^{2n+1} -1^{\lfloor k/2\rfloor+n-k}\left(\begin{array}{c}n\\\lfloor k/2\rfloor\end{array}\right)x^{n-k}y^{k}$$

This can be shown to be equal to $x(x^2-y^2)^n -y(x^2-y^2)^n = (x-y)(x^2-y^2)^n$ which is equal to $(x-y)^{n+1}(x+y)^n$.

We can repeat the coefficients more than 2 times as well and show that

$$\sum_{k=0}^{m(n+1)-1} \left(\begin{array}{c}n\\\lfloor k/m\rfloor\end{array}\right)x^ky^{n-k}$$

is equal to $\sum_{t=0}^{t=m-1}x^ty^{m-1-t}(x^m+y^m)^n$.

## Friday, January 20, 2017

### Interesting number: 1440000

The number 1440000 satisfies the following equation:

$$1440000^3 - 1 = 1439940^3 + 71999^3 = 1440060^3 - 72001^3$$

By Fermat's Last Theorem (for which the case $n=3$ was proven by Euler), $1440000^3$ cannot be the sum or difference of 2 positive integer cubes. The above equation shows that $1440000^3-1$ is the sum and the difference of 2 positive integer cubes.

## Thursday, January 12, 2017

### March or May?

I looked at the expiration date on a tube of toothpaste today and it said: MA17.  Is it March 2017 or May 2017? There doesn't seem to be a standard 2-digit abbreviation for the English names of months.

### Number of 2 by 2 matrices with all elements in {0,1,..,n} and its permanent equal to the sum of all elements

OEIS sequence A280934 is defined as: $a(n) =$ the number of 2 by 2 matrices with all elements integers in the set $\{0,1,..,n\}$ and its permanent is equal to the sum of all elements.

Consider a 2 by 2 matrix $\left(\begin{array}{cc}a & c \\ d & b\end{array}\right)$. The sum of all elements equal to the permanent is written as $a+b+c+d = ab+cd$. This can be rewritten as $(a-1)(b-1) + (c-1)(d-1) = 2$. In other words, $a(n) =$ the number of 2 by 2 matrices with all elements integers in the set $\{-1,..,n-1\}$ and its permanent is equal to 2. We will consider this alternative formulation in the rest of this note. Suppose $n > 3$ and at least one of members of the matrix has value $n-1$. Let us count how many of such matrices has permanent 2, i.e. $ab+cd = 2$.

First consider the case $a = n-1$. If  $b = -1$, then $cd = n+1$. Note that $c \neq 1$ and $c \neq n+1$ since $-1\leq c,d\leq n-1$. Since $n> 3$, any nontrivial factor of $n+1$ is less than $n-1$. Thus setting $c>1$ equal to any nontrivial factor of $n+1$ and $d = (n+1)/c$ will result in a matrix with permanent 2. Thus there are $\tau(n+1)-2$ such matrices. Here $\tau(n)$ denotes the number of divisors of $n$. If $b = 0$, then $cd = 2$ and there are 2 cases: $(c,d) = (1,2)$ and $(c,d) = (2,1)$. If $b=1$, then $cd = 3-n$ and there are 2 cases as well: $(c,d) = (-1,n-3)$ and $(c,d) = (n-3,-1)$. Note that $cd \geq 1-n$ since $-1\leq c,d\leq n-1$. This means that if $b > 1$ then $ab+cd \geq n-1 > 2$. Thus we have a total of $\tau(n+1)+2$ cases. Note that in all cases, exactly one element of the matrix is of value $n-1$.

By symmetry, the same analysis applies to $b=n-1$, $c=n-1$ and $d=n-1$ as well. Since in all the cases only one element of the matrix is of value $n-1$, there is no double counting. Thus the number of matrices with at least one member equal to $n-1$ and permanent 2 is $4\tau(n+1)+8$. This implies the following recurrence relation for $a(n)$:

$$a(n) = a(n-1) + 4\tau(n+1)+8 \quad\mbox{for}\quad n> 3$$.

## Saturday, November 5, 2016

### "Bots" creating news digests about "bots"

I use a news digest app on my phone to read a selection of important news in areas I selected. This is nice since it only lists news items that I am most likely interested in and saves me time in reading the day's news.  I think the news summary is created automatically via computer algorithms, since many times the highlighted quote does not make sense or is attributed to the wrong person.  In addition, the "to explore further" section sometimes points to unrelated and/or inappropriate Wikipedia articles. Sometimes, this is because the person in the news has the same name as someone who is much more famous, so the Wikipedia article is about the wrong (but more well known) person.

Today, in the "science" section, there is a summary digest article about news organizations utilizing "bots", or automatic algorithms to aggregate data and generate news article. It is quite amusing, since again the highlighted quote is attributed to the wrong person and the "to explore further" section points to a specific news paper and is tangentially related to the news article.

## Wednesday, September 28, 2016

In Chinese slang, the phrase "加油", literally translated as "add oil", means "put more effort" and is typically used as encouragement to try harder in order to succeed at something. I believe the origin come from the fact that we need to add oil (gasoline) to cars in order for it to move. As we are all expected to drive electric or hydrogen cars in the future, this might become an archaic slang in the not too distant future.

In an earlier blog post$\delta(n)$ is defined as the smallest term in the periodic part of the continued fraction of $\sqrt{n}$ and I showed that if $r$ is even then $\delta((\frac{rm}{2})^2+m) = r$ for all $m\geq 1$. and if $r$ is odd, then $\delta((rm)^2+2m) = r$ for all $m\geq 1$. Note that $\delta(n)$ is only defined if $n$ is not a perfect square.
If you look at the first few numbers $n$ that satisfy $\delta(n) = r$, it would appear that they all follow the quadratric equations above. However, not all integers $n$ such that $\delta(n) = r$ are of the forms above. In particular, if $r > 0$ is even, then $\sqrt{\frac{r^4}{4} + r^3 + 2r^2 + 3r + 2} = \sqrt{\frac{(r^2-2)^2}{4}+(r+1)^3}$ has continued fraction expansion $\left[\frac{(r+1)^2+1}{2};\overline{r+1,r,r+1,(r+1)^2+1}\right]$ and thus $\delta\left(\frac{r^4}{4} + r^3 + 2r^2 + 3r + 2\right) = r$ and it is not of the forms above.
Similarly, if $r$ is odd, then $\sqrt{r^4 + r^3 + \frac{5(r+1)^2}{4}}$ has continued fraction expansion $\left[\frac{(r+1)(2r-1)+2}{2};\overline{r,2r-1,r,(r+1)(2r-1)+2}\right]$ and thus $\delta\left(r^4 + r^3 + \frac{5(r+1)^2}{4}\right) = r$ and it is not of the forms above either.