6
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ The function for $\alpha$ is too implicit. I tried calculating the next term for $a_3$, but I don't know how to continue. How can you calculate $a_3$? I tried figuring it out, but I got $a_3 = 4$, assuming you ignore the value for $\alpha$ if one doesn't know what the value of $\alpha$ is. $\endgroup$ Jul 30 at 23:29

1 Answer 1

2
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Very nice proof! $\endgroup$ Feb 20, 2015 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, 2015 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, 2015 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.