Fibonacci Numbers Everywhere?

September 19, 2011

Let a_n be a sequence with values in \mathbb{N} and let

\alpha(n):=\min\{m\in\mathbb{N}: n|a_m\}

be the first index m such that n divides a_m whenever it exists (otherwise it stays undefined). Next define a sequence by the following recurrence:

a_1:=1

and

a_{x+2}:= 1+\sum_{n:\alpha(n)\leq x} \varphi(n) \left\lfloor\frac{x}{\alpha(n)}\right\rfloor

for 0\leq x\in\mathbb{N }. Here, \varphi denotes Euler’s totient function. Note that the sum is extended over all n with \alpha(n)\leq x. The values of \alphaare thus defined. Moreover, the sum is finite.

What is a_n? As it turns out and as you might have guessed from the title a_n is the well-known Fibonacci series.

Computational example. Assume we knew that the a_n were the Fibonacci numbers for 1\leq i\leq 5. Then  a_7 = 1+\sum_{n\in\{1, 2, 3, 5\}}\varphi(n)\left\lfloor\frac{x}{\alpha(n)}\right\rfloor where the sum is extended over all divisors of a_1, \ldots , a_5 (i.e. the divisors of 1, 1, 2, 3, 5). Thus

a_7 = 1+1 \left\lfloor\frac{5}{1}\right\rfloor+1 \left\lfloor\frac{5}{3}\right\rfloor+2\left\lfloor\frac{5}{4}\right\rfloor+4 \left\lfloor\frac{5}{5}\right\rfloor = 13.

How does one prove that the a_n are indeed the Fibonacci numbers? Actually, there is a nice and elementary double counting proof for this and even after scribbling it down I must confess that for me the Fibonacci numbers here somehow pop out of nowhere.

Leave a Comment » | Recreational Mathematics | Tagged: , , | Permalink
Posted by Uwe Stroinski