Relación de recurrencia satisfecho por $\lfloor(1+\sqrt{5})^n\rfloor$

Question

Que $L(n)=\lfloor(1+\sqrt{5})^n\rfloor$. ¿Qué tipo de una repetición linear está satisfecha por $L(n)$? No tengo ni idea de cómo ir sobre esto, debido a la presencia de la función entero mayor.

Por favor, no dude en cambiar la etiqueta como me seguí poniendo error en cada etiqueta que pensé que era apropiado.

Answer 1

¿Tiene usted alguna razón para sospechar $L(n)$ debe satisfacer una recurrencia lineal? Aquí hay una manera de demostrar que no satisface una recurrencia lineal de la profundidad de 2 (que puede ser generalizado a cualquier profundidad).

Paso 1: Calcular $L(n)$ para las pequeñas $n$: 3, 10, 33, 109, 354, 1148, 3716, ...

Paso 2: Suponga $b L(n-2)+a L(n-1)=L(n)$ algunos $a,b$. Utilizando los datos del Paso 1, obtenemos el sistema de ecuaciones lineales:

• $3b+10a=33$,
• $10b+33a=109$,
• $33b+109a=354$.

De hecho, se puede mantener siempre va añadiendo ecuaciones $109b+354a=1148$, y así sucesivamente.

Paso 3: Resolver el sistema de ecuaciones lineales (o de conseguir que su equipo lo haga por usted (utilizando, por ejemplo, WolframAlpha)). En este caso no hay soluciones, por lo $L(n)$ no satisface una recurrencia lineal de la profundidad de 2. Si usted siente que el punto de partida no debería ser $L(1)$, se puede utilizar el mismo argumento de partida más tarde en la secuencia.

Suponiendo que yo codificado cosas correctamente, he comprobado que el $L(n)$ no satisface una recurrencia lineal de profundidad 10 (o menos). [Es probablemente una buena idea para comprobar esto si usted termina de confiar en este resultado.] También he intentado encontrar una recurrencia lineal con coeficientes polinomiales para $L(n)$ a un alcance limitado (ver A=B acerca de la Hermana Celine la Técnica para obtener más información).

Por último, si usted está autorizado a utilizar una función auxiliar, luego deje $s(1)=1+\sqrt{5}$ $n \geq 2$ deje $s(n)=(1+\sqrt{5}) \cdot s(n-1)$. A continuación, $L(n)=\lfloor s(n) \rfloor$ todos los $n \geq 1$.