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

  • 1
    $\begingroup$ Very nice proof! $\endgroup$ Feb 20 '15 at 14:12
  • $\begingroup$ 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. $\endgroup$ Feb 20 '15 at 14:20
  • 1
    $\begingroup$ the proposition holds, because the numbers $a_1,⋯,a_{x+1}$ are the first Fibonacci numbers (Induction Hypothesis), I changed a little the proposition $\endgroup$
    – Elaqqad
    Feb 20 '15 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.