Busco una solución $f$ a la ecuación de diferencia $$f(i)=2(f(i-1)+f(\lceil i/2\rceil))$$ con $f(2)=4$ . Muy agradecido por cualquier idea.
PS. He intentado trazar los valores iniciales en "Sloan", pero no parece reconocer la secuencia.
Respuestas
¿Demasiados anuncios?
Desde $f$ es siempre positivo, $f(i) \gt 2f(i-1)$ y así por inducción $f(n) \gt 2^n$ . $f(\lceil i/2\rceil)$ es exponencialmente menor que $f(i)$ Así que $2^n$ es el término dominante. Divide $f$ por la exponencial y definir $g(n) = 2^{-n}f(n)$ Entonces $g(i) = g(i-1) + 2^{1-\lfloor i/2\rfloor}g(\lceil i/2\rceil)$ con $g(2)=1$ . Es fácil ver por inducción que $g(n) \lt n$ y de hecho $g(n) = O(n^\epsilon)$ para cualquier $\epsilon$ (las diferencias para una serie de $\Theta(n^\epsilon)$ son $\Theta(n^{\epsilon-1}) = {n^\epsilon\over n}$ que finalmente es mayor que $n^{\epsilon}\over2^\epsilon2^{n/2}$ para cualquier $\epsilon$ ). De hecho, la forma de la serie sugiere vagamente que $g(n)$ puede ser alguna constante exponencialmente amortiguada, aproximadamente $C+\Theta(2^{-kn})$ para algunos $k$ y $C$ ; podrías intentarlo desde esa perspectiva...
Eric Naslund
Puntos
50150
Por métodos numéricos calculé los primeros 10000, y $f(n)$ convergieron muy rápidamente hacia $$C2^n$$ donde $C=6.431946109729$ . En otras palabras, $$f(n)\sim 1.607986527432\cdot 2^{n+2}.$$ Mi esperanza era que si $C$ fuera una constante conocida, esto nos diría más sobre el problema. Por desgracia, ninguna de las constantes anteriores aparecía en la calculadora simbólica inversa.
Fabian
Puntos
12538
Para el comportamiento asintótico, sólo es importante el primer término del lado derecho; imaginemos que la serie crece rápidamente -- como pronto veremos que es cierto -- entonces el término $f(i/2)$ es mucho menor que $f(i-1)$ . La ecuación $$f(i) \sim 2 f(i-1)$$ se puede resolver fácilmente y se obtiene $$f(i) \sim c\, 2^i$$ donde $c$ es una constante. Por lo tanto $f(i) = \Theta(2^i)$ .
