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