Conexión entre la función totiente de Euler y los números de Fibonacci

Question

Para una secuencia $(a_n)$ de números naturales definen $\alpha(n):=\min\{m\in\mathbb{N}:n|a_m\}$ siempre que exista. Así, $\alpha(n)$ es el primer índice $m$ tal que $n$ divide $a_m$ .

Ahora define la siguiente secuencia. Configure $a_1:=1, a_2:=1$ y $$a_{x+2}:= 1 + \sum_{n:\alpha(n)\leq x}\varphi(n)\left\lfloor\frac{x}{\alpha(n)}\right\rfloor$$ para $x\geq 1$ . La suma está destinada a todos los $n$ que dividen al menos una $a_m$ con $m\leq x$ . $\varphi$ es la función totiente de Euler. Se puede demostrar que es la sucesión de Fibonacci.

Mi sospecha es que lo anterior no es más que una forma enrevesada de enunciar alguna conexión conocida o incluso obvia entre la función totiente de Euler y los números de Fibonacci. ¿Qué se me escapa?

P: Me gustaría tener una referencia (en caso de ser muy conocido) o una prueba breve (en caso de ser obvio).

Answer 1

No sé si podemos usar la convolución para probar tu afirmación, y es la primera vez que lo veo así que no conozco ninguna referencia , Pero tengo una prueba por inducción.

Los primeros términos $a_1,a_2$ coinciden con los números de Fibonacci.

Supongamos que: $a_1,a_2,\cdots,a_{x},a_{x+1}$ son los primeros números de Fibonacci (esta suposición se utiliza en la proposición) y demostrar que $a_{x+2}$ es el siguiente número de Fibonacci.

calculamos $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 )$$ Y sabemos que $\lfloor x/k \rfloor - \lfloor (x-1)/k \rfloor = 1$ cuando $k|x$ (para $k\geq1$ ) y $0$ de lo contrario, así que $$a_{x+2}-a_{x+1}=\sum_{n:\alpha(n)|x} \varphi(n)\,\,\,\, (1)$$ pero tenemos

Propuesta para cada número entero positivo $n$ $$\alpha(n)|x \Leftrightarrow n|a_x$$

prueba primero está claro que si $\alpha(n)=k$ con $k|x$ entonces $n|a_k$ y porque $a_k$ y $a_x$ son números de Fibonacci, entonces $a_k|a_x$ finalmente $n|a_x$ .

En segundo lugar, dado un divisor $n$ de $a_x$ dejemos $\alpha(n)=k\leq x$ entonces $n|a_k$ así que $n|gcd(a_k,a_x)=a_{gcd(x,k)}$ ( porque $a_x$ y $a_k$ son números de Fibonacci) utilizando la definición de $\alpha(n)$ tenemos $k\leq gcd(x,k)$ de ahí $k|x$ .

Utilizando la proposición, la suma $(1)$ se convierte: $$a_{x+2}-a_{x+1}=\sum_{n:n|a_x} \varphi(n)$$ utilizando la identidad de Euler $\sum_{d:d|n} \varphi(d)=n$ : $$a_{x+2}-a_{x+1}=a_x$$

Por último $a_{x+2}$ es el siguiente número de Fibonacci