## Archive for December, 2011

### A proof from the book

December 16, 2011

We shall prove the following identity:

$1 + 2 + 4 + 8 + .. + 2^{k-1} = 2^k - 1$,

with perhaps the most beautiful proof I have ever found.

Assume that we play a tournament with $2^k$ players, in which every game is a knock-out game between $2$ players. So in the first round there are $2^{k-1}$ games to be played, one for every $2$ people. Then in the second round only half of the players remains (i.e. $2^{k-1}$), so there are another $2^{k-2}$ games to be played, and so forth. Right up to the semi final and final, which are just $2^1$ and $2^0 = 1$ games, respectively. So the total amount of games played in the tournament is: $1 + 2 + 4 + 8 + .. + 2^{k-1}$. Another way to see how many games total there are played is the following: in every game, exactly $1$ player gets eliminated. There is only one winner, so the other $2^k - 1$ players must get elimated somewhere. So the total amount of games played must equal $2^k - 1$. Kablam.

### Conjecture concerning sequences with a lot of consecutive elements with small lcm

December 7, 2011

Let $1 \le a_1 < a_2 < ..$ be an infinite sequence of positive integers, such that, if we define $A(n)$ to be the number of indices $i$ such that $\text{lcm}(a_i, a_{i+1})\le n$, then we have for every $\epsilon > 0$ infinitely many $n$ such that $A(n) > (c - \epsilon)\sqrt{n}$, where $c = \displaystyle \sum_{j=1}^{\infty} \dfrac{1}{(j+1)\sqrt{j}} \approx 1.86$. In my previous post I claimed that such sequences exist, and in due time I will prove this claim, but for now, let’s assume it.

Now, let $\epsilon$ be small and $n_1 < n_2 < ..$ be the sequence of all $n$ such that $A(n) > (c - \epsilon)\sqrt{n}$. Then I’d like to bluntly conjecture that there exist infinitely many $i$ such that $\dfrac{n_{i+1}}{n_i} > c_1\epsilon^{-4}$, for some absolute $c_1$. In particular, $\displaystyle \limsup \dfrac{n_{i+1}}{n_i}$ goes to $\infty$ as $\epsilon$ goes to $0$, that is: $\displaystyle \lim_{\epsilon \rightarrow 0} \limsup_{i \rightarrow \infty} \dfrac{n_{i+1}}{n_i} = \infty$

### Sequences with bounded lcm for consecutive elements

December 6, 2011

On page 83 of the pdf-file of Old and New Problems and Results in Combinatorial Number Theory, the following is asked: If we have an infinite sequence $1 \le a_1 < a_2 < ..$ of positive integers and set $A(n)$ to be the number of indices $i$ such that $\text{lcm}(a_i, a_{i+1}) \le n$, do we then have $A(n) = O(\sqrt{n})$? In the following very short article I answer the finite version of this question, which also implies an affirmative answer to the original question: Sequences with bounded lcm for consecutive elements . I conjecture that the term $\log(2n)$ is superfluous, but to get rid of it completely, a more detailed approach is needed. By the way, the constant $c \approx 1.86$ is best possible, in the sense that it is possible to construct an infinite sequence such that, for every $\epsilon > 0$ and infinitely many $n$, we have $A(n) > (c-\epsilon)\sqrt{n}$.

### Hello World!

December 6, 2011

A reminder for myself: my name is woutervandoorn