Fibonacci Numbers Everywhere?

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: