September « 2011 « Random Thoughts

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 $\alpha$ are 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: Fibonacci Number, Mathematics, Recreational Mathmatics | Permalink
Posted by Uwe Stroinski