Tengo curiosidad por cómo uno se puede dar cuenta de redondeo en simples relaciones de recurrencia.
$\textbf{Explanation}$
Para un problema concreto, supongamos que tenemos una secuencia de enteros positivos $a_1, a_2, a_3,...$ con donde cada una de las $a_i$ obedece a la siguiente regla $$a_n=a_{n-1}+\text{floor}\Big[\frac{a_{n-4}}{2}\Big]$$ Donde "piso" aquí sólo redondee hacia abajo. Por ejemplo, si $a_1=5$ $a_4=7$ $$a_5=7+\text{floor}\Big[\frac{5}{2}\Big]=9$$
Y si empezamos con $a_1=a_2=a_3=a_4=6$ y continuar la secuencia obtenemos $$6\rightarrow6\rightarrow6\rightarrow6\rightarrow9\rightarrow12\rightarrow15\rightarrow18\rightarrow22\rightarrow28\rightarrow35\rightarrow44\rightarrow55\rightarrow...$$ ¿Qué es $a_{100}$? Y lo que es más importante, puede $a_n$, en general, ser exactamente calculado sin calcular todos los términos anteriores en la secuencia?
He aquí lo que se ha intentado hasta ahora
$\textbf{Linear Algebra Approximation}$
La regla de actualización de la secuencia anterior se puede aproximar con una transformación lineal $$ A = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \frac{1}{2} & 0 & 0 & 0 \\ \end{bmatrix} \quad \quad \text{con} \quad \quad A \cdot \begin{bmatrix} a_n \\ b_n \\ c_n \\ d_n \\ \end{bmatrix} = \begin{bmatrix} a_{n+1} \\ b_{n+1} \\ c_{n+1} \\ d_{n+1} \\ \end{bmatrix} $$ donde el $a_n$ en cada vector se corresponde con el mismo $a_n$ de la secuencia anterior ejemplo.
Esta matriz tiene sólo uno de todos los positivos autovector con un autovalor $\lambda=1.254...$ que es la tasa de crecimiento se acercó por la secuencia. Uno podría predecir el valor de $a_n$ mediante el cálculo de $$A^n \cdot \begin{bmatrix} a_1 \\ a_1 \\ a_1 \\ a_1 \\ \end{bmatrix}$$
El problema con el uso de una transformación lineal es que el redondeo no es tomada en cuenta. Así las predicciones uno llega inevitablemente el sobregiro. Y algunos a partir de las secuencias de no aumentar aún cuando el redondeo es tomado en cuenta. Considere la posibilidad de $a_1=a_2=a_3=a_4=1$ $$1\rightarrow1\rightarrow1\rightarrow1\rightarrow1\rightarrow1\rightarrow1\rightarrow1\rightarrow...$$
$\textbf{Error Estimation}$
Para los valores iniciales de la secuencia que muy divisible por $2$, el redondeo hacia abajo no afectan a la secuencia de un tiempo más largo.
Más específicamente, si empezamos con los $$a_1=a_2=a_3=a_4=k2^m \text{ where } k \text{ is odd}$$ A continuación, $a_{4m+5}$ será el primer término afectados por el redondeo. Uno podría introducir un error de redondeo de la función. Algo de la forma $$f(k, m) = \text{% error approached by the initial value } k2^m$$
Se sugirió utilizar lineal de la dinámica de sistemas discretos para derivar una fórmula exacta para $a_n$. ¿Cómo es exactamente que está hecho es aún desconocido. ¿Hay algún buen ejemplo de problemas similares a este?
