La forma cerrada para la suma de incluso los números de fibonacci?

Question

Recientemente tomé un vistazo a un proyecto de euler, y estoy tratando de pensar en una manera inteligente de hacer el número 2. Miré a la secuencia, y vi que la pregunta es, básicamente para $$\sum_{i=1}^n F_{3i}$$

Por lo que n es que me da la enésima incluso menos de un millón. Así que, hice un poco de tocar el violín alrededor con esto, y tengo esto para ser equivalente a

$$\sum_{i=0}^{n-1} F_{3i-1}(3^{n-i}-1)$$

Me preguntaba, ¿existe aún una forma cerrada para algo como esto? O estoy perdiendo mi tiempo? No podía encontrar una forma cerrada en línea en cualquier lugar.

Answer 1

$$F_k=\frac{\left(1+\sqrt{5}\right)^k}{2^k\sqrt{5}}-\frac{\left(1-\sqrt{5}\right)^k}{2^k\sqrt{5}}$$ $$\sum_{k=1}^nF_{3k}=\sum_{k=1}^n\frac{\left(1+\sqrt{5}\right)^{3k}}{2^{3k}\sqrt{5}}-\sum_{k=1}^n\frac{\left(1-\sqrt{5}\right)^{3k}}{2^{3k}\sqrt{5}}$$ $$=\frac{1}{\sqrt5}\sum_{k=1}^n\left(\frac{1+\sqrt{5}}{2}\right)^{3k}-\frac{1}{\sqrt5}\sum_{k=1}^n\left(\frac{1-\sqrt{5}}{2}\right)^{3k}$$ $$\text{ but we have , } x^3+x^6+x^9...x^{3n}=x^3\frac{x^{3n}-1}{x^3-1}$$ $$\text{ so then, }$$ $$=\frac{1}{\sqrt5}\sum_{k=1}^n\left(\frac{1+\sqrt{5}}{2}\right)^{3k}-\frac{1}{\sqrt5}\sum_{k=1}^n\left(\frac{1-\sqrt{5}}{2}\right)^{3k}$$ $$=\frac{1}{\sqrt5}\left(\left(\frac{1+\sqrt{5}}{2}\right)^3\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{3n}-1}{\left(\frac{1+\sqrt{5}}{2}\right)^3-1}-\left(\frac{1-\sqrt{5}}{2}\right)^3\frac{\left(\frac{1-\sqrt{5}}{2}\right)^{3n}-1}{\left(\frac{1-\sqrt{5}}{2}\right)^3-1}\right)=\frac{F_{3n+2}-1}{2}$$

$$=\sum_{k=1}^{n}F_{3k}$$

Answer 2

Esta respuesta no dar una forma cerrada, pero sí se da una forma de calcular esta suma.

El general de la forma cerrada, todavía no es siempre útil para el cálculo, debido a que usted necesita para ser capaz de calcular los valores reales de gran precisión.

También tenga en cuenta que yo comienzo a las $i=0$. Esto no afecta en nada ya que $F_0=0$.

Esta respuesta requiere algo sofisticado conocimiento acerca de recurrencias lineales.

Hay una forma cerrada para $F_n = a_1\alpha_1^n + a_2\alpha_2^n$ para algunos números reales $a_1,\alpha_1,a_2,\alpha_2$. Entonces:

$$\begin{align}G_n = \sum_{i=0}^n F_{3i} &= a_1\frac{\alpha_i^{3n+3} -1}{\alpha_1-1}+a_2\frac{\alpha_2^{3n+3} -1}{\alpha_2-1}\\ &=b_1\alpha_1^{3n} + b_2\alpha_2^{3n} + b_3\cdot 1^n \end{align}$$

para algunos $b_1,b_2,b_3$.

Ahora que usted necesita saber un poco acerca de este tipo de recursivas relación lineal, pero si nos fijamos en el polinomio $(x-\alpha_1^3)(x-\alpha_2^3)(x-1) = (x^2-4x-1)(x-1) = x^3-5x^2+3x+1$, esto produce una relación de recurrencia:

$$G_{n+3} = 5G_{n+2} -3G_{n+1} - G_{n}$$

Que le da un recursiva para calcular su suma, $G_n$ en general.

Otro enfoque es el uso de la matriz de la fórmula:

$$\left(\begin{matrix}1 & 1\\1&0\end{matrix}\right)^n = \left(\begin{matrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{matrix}\right)$$

Si $A=\left(\begin{matrix}1 & 1\\1&0\end{matrix}\right)$, entonces la serie $\sum_{i=0}^n A^{3i}$, en la diagonal, la suma que desee.

Pero usted consigue la suma normal de un geomtric de la serie:

$$\sum_{i=0}^n A^{3i} = (A^{3n+3}-I)(A^3-I)^{-1}$$

Ahora, $A$ satisface una ecuación, $A^2 - A - I = 0$, y por lo tanto $A^3-I=2A$. También se $A^{-1} = A-I$, por lo que desea calcular: $$\frac{1}{2}(A^{3n+3} - I)(A-I)$$

Ahora, podría no parecer mucho más fácil para calcular $A^{3n+3}$, pero se puede hacer eso con sólo $O(\log(3n+3))$ multiplicaciones utilizando el método de la exponenciación al cuadrado.

una vez que se ha calculado la matriz, tomar el valor fuera de la diagonal.

Ivan Loh a continuación tomó nota de que podemos hacerlo mejor en un comentario en la otra respuesta, y se aplica aquí también. Sabemos $A^{3n+3}$, así que podemos escribir todo esto como:

$$\begin{align}(A^{3n+3}-I)(A-I) &= \frac 1 2 \left(\begin{matrix}F_{3n+4}-1&F_{3n+3}\\F_{3n+3}&F_{3n+2}-1\end{de la matriz}\right)\left(\begin{matrix}0 & 1\\ 1 & -1\end{de la matriz}\right)\\ &=\frac{1}{2}\left(\begin{matrix}*&*\\F_{3n+2}-1&*\end{de la matriz}\right) \end{align}$$

(No nos importa el resto de las entradas.)

Por lo que la suma que estamos buscando es $\frac{F_{3n+2}-1}{2}$.

Answer 3

Para la variedad, si $\varphi$ es la proporción áurea, entonces

$$\varphi^n = F_{n-1} + F_n \varphi$$

(donde $F_0 = 0$ $F_1 = 1$ ... y $F_{-1} = 1$) de La misma ecuación tiene por $\bar{\varphi}$, la otra raíz de $x^2 = x+1$. (no es el complejo conjugado)

Por lo tanto

$$\sum_{i=0}^n \varphi^{3i} = (\cdots) + \left(\sum_{i=0}^n F_{3i} \right) \varphi$$

Podemos deshacernos de los no deseados plazo por restando de su conjugado:

$$\sum_{i=0}^n \varphi^{3i} - \bar{\varphi}^{3i} = \left(\sum_{i=0}^n F_{3i} \right) (\varphi - \bar{\varphi})$$

Y entonces usted puede hacer lo que quiera a partir de ahí. Este es, por supuesto, de forma similar a las otras respuestas; simplemente me gusta cómo se organiza.