La generación de la función solución de la pregunta anterior $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

Question

En el intento de responder a esta pregunta, me la redujo a un aparentemente simple, la generación de las funciones de la pregunta, pero después de días de trabajo, fue capaz de construir una prueba. Ya que no tengo experiencia tratando de hacer asymptotics con funciones de generación, me gustaría saber si una prueba es rescatable de estos métodos.

El problema que presenta la secuencia de $a_n$, que se define por $a_0 = 1$ y $$ a_{n}=a_{\left\lfloor n/2\right\rfloor}+a_{\left\lfloor n/3 \right\rfloor}+a_{\left\lfloor n/6\right\rfloor} $$ y pide una prueba de que $$ \lim_{n\to\infty}\dfrac{a_{n}}{n}=\dfrac{12}{\log{432}}. $$ La escritura de la generación de la función $\displaystyle Una(x) = \sum_{n \ge 0} a_n x^n$, esto se traduce en $$ Una(x) = (1 + x)a(x^2) + (1 + x + x^2) (x^3) + (1 + x + x^2 + \cdots + x^5) (x^6) - 2 $$

Mejor aún, deje de $b_0 = a_0$ y $b_n = a_n - a_{n-1}$ para todo $n \ge 1$, y definir la generación de la función $\displaystyle B(x) = \sum_{n \ge 0} b_n x^n = (1 - x)a(x)$. Multiplicando el anterior por $(1-x)$ da $$ (1 - x)a(x) = (1 - x^2) (x^2) + (1 - x^3) (x^3) + (1 - x^6) (x^6) + 2x - 2 $$ es decir, $$ B(x) = B(x^2) + B(x^3) + B(x^6) + 2x - 2 \etiqueta{1} $$

Después, sin éxito, tratando de hacer assymptotics con el anterior elegante fórmula, la he usado para encontrar una representación explícita de $B$, el uso de la Delannoy Números:

$$ B(x) = 1 + 2 \sum_{l, m \ge 0} \sum_{d \ge 0} 2^d {l \elegir d}{m \elegir d} x^{2^l 3^m} $$

De ello se desprende que, de hecho, $$ a_n=1+2\sum_{d\ge0}2^d\sum_{\begin{matriz}l,m\ge0\\2^l 3^m \le n\end{matriz}}{l \elegir d}{m \elegir d} \etiqueta{2} $$

Uno puede hacer ingenuo de los límites de la suma en (2) - sustitución de la condición de $2^l 3^m \le n$ con $2^l 2^m \le n$ y $3^l 3^m \le$ n para los límites superior e inferior, respectivamente. Pero esto no es suficiente; da (después de álgebra y combinatoria de trabajo) aproximadamente $$ \frac{n^{\log_3(1 + \sqrt{2}) - 1}}{2} < \frac{a_n}{n} < \frac{n^{\log_2(1 + \sqrt{2}) - 1}}{2} $$

Esto parece sugerir tratando de aproximarse (2) con la condición de $(1 + \sqrt{2})^l (1 + \sqrt{2})^m \le$ n, pero no tengo idea de cómo justificar que.

En cualquier caso, he hecho demasiado de lo que se siente como progreso a dar hasta en el problema, y si alguien puede pensar en una forma de uso (2) para obtener una solución o de lo contrario el uso de (1) y encontrar el asymptotics directamente, yo estaría muy agradecido.

Answer 1

El "maestro teorema" por Leighton es aplicable. Para una recurrencia $T(z) = g(z) + \sum_{1 \le k \le n} a_k T(b_k z + h_k(z))$, donde $z \ge 0$, tal que hay suficiente base de los casos; la totalidad de los $a_k > 0$ y $0 < b_k < 1$; hay una constante $c$ tal que $\lvert g(z) \rvert = O(c^z)$; y todo $\lvert h_k(z)\rvert = S(z /(\log z)^2$. Entonces para $p$ tal que $\sum_{1 \le k \le n} a_k b_k^p = 1$, la solución que satisface:

$$ T(z) = \Theta \left( z^p \left( 1 + \int_1^z \frac{g(u)}{u^{p + 1}} \, \mathrm{d} u \right) \right) $$

El $h_k$ son fudge factores, que cubren casos como el de la diferencia de los pisos y techos.

Aquí tenemos $g(z) = 0$, $a_1 = a_2 = a_3 = 1$, $b_1 = 1/2$, $b_2 = 1/3$, y $b_3 = 1/6$, de modo que $p = 1$. Con $g(z) = 0$, el teorema nos dice que $a_n = \Theta(n)$.

Answer 2

Una completa solución asintótica exactamente este tipo de recurrencias se deriva por Erdös et al "El Comportamiento Asintótico de una Familia de Secuencias de" Pacific Journal of Mathematics 126:2 (1987), pp 227-241. Que el uso de este exacto de recurrencia como un ejemplo, y muestran que:

$$ a_n \sim \frac{12}{\log 432} n $$