# Connection between Euler's totient function and Fibonacci numbers

For a sequence $(a_n)$ of natural numbers define $\alpha(n):=\min\{m\in\mathbb{N}:n|a_m\}$ whenever it exists. Thus $\alpha(n)$ is the first index $m$ such that $n$ divides $a_m$.

Now define the following sequence. Set $a_1:=1, a_2:=1$ and $$a_{x+2}:= 1 + \sum_{n:\alpha(n)\leq x}\varphi(n)\left\lfloor\frac{x}{\alpha(n)}\right\rfloor$$ for $x\geq 1$. The sum is meant to be taken over all $n$ that divide at least one $a_m$ with $m\leq x$. $\varphi$ is Euler's totient function. One can show that this is the Fibonacci sequence.

My suspicion is that the above is just a convoluted way to state some well-known or even obvious connection between Euler's totient function and the Fibonacci numbers. What am I missing?

Q: I would like to have a reference (in case of well-known) or a short proof (in case of obvious).

I don't know if we can use convolution to prove your statement, and it's the first time i see it so I don't know any reference , But I have a proof by induction.

The first terms $a_1,a_2$ coincide with Fibonacci numbers.

Let us suppose that:$a_1,a_2,\cdots,a_{x},a_{x+1}$ are the first Fibonacci numbers (this assumption is used in the proposition) and prove that $a_{x+2}$ is the next Fibonacci number.

we compute $a_{x+2}-a_{x+1}$: $$a_{x+2}-a_{x+1}=\sum_{n:\alpha(n)=x} \varphi(n)+\sum_{n:\alpha(n)<x-1}\varphi(n) \left (\left \lfloor{ \frac{x}{\alpha(n)} }\right \rfloor - \left \lfloor{ \frac{x-1}{\alpha(n)} }\right \rfloor\right )$$ And we know that $\lfloor x/k \rfloor - \lfloor (x-1)/k \rfloor = 1$ when $k|x$ (for $k\geq1$) and $0$ otherwise, so $$a_{x+2}-a_{x+1}=\sum_{n:\alpha(n)|x} \varphi(n)\,\,\,\, (1)$$ but we have

Proposition for every positive integer $n$ $$\alpha(n)|x \Leftrightarrow n|a_x$$

proof first it's clear that if $\alpha(n)=k$ with $k|x$ then $n|a_k$, and because $a_k$ and $a_x$ are Fibonacci numbers then $a_k|a_x$ finally $n|a_x$.

Second, given a divisor $n$ of $a_x$,let $\alpha(n)=k\leq x$ then $n|a_k$ so $n|gcd(a_k,a_x)=a_{gcd(x,k)}$ ( because $a_x$ and $a_k$ are Fibonacci numbers) using the definition of $\alpha(n)$ we have $k\leq gcd(x,k)$ hence $k|x$.

Using the proposition, the sum $(1)$ becomes: $$a_{x+2}-a_{x+1}=\sum_{n:n|a_x} \varphi(n)$$ using Euler's identity $\sum_{d:d|n} \varphi(d)=n$ : $$a_{x+2}-a_{x+1}=a_x$$

Finally $a_{x+2}$ is the next Fibonacci number

• Very nice proof! – Uwe Stroinski Feb 20 '15 at 14:12
• Technically you are not allowed to use the proposition, since the alpha_n is implicitely defined by the a_n and we do not know whether the proposition holds at that stage. However, I am sure that this can be fixed in a line or two. – Uwe Stroinski Feb 20 '15 at 14:20
• the proposition holds, because the numbers $a_1,⋯,a_{x+1}$ are the first Fibonacci numbers (Induction Hypothesis), I changed a little the proposition – Elaqqad Feb 20 '15 at 14:26