Hay una discreta versión de de l'Hôpital de la regla?

Question

Al considerar asymptotics de funciones de tiempo de ejecución, que a menudo tienen que encontrar los límites de cocientes de funciones discretas, por ejemplo,

$\displaystyle\qquad \lim\limits_{n \to \infty} \frac{4^n}{\binom{2n}{n}\sqrt{n}}.$

Mientras que en este caso particular puede ser fácilmente tratada por la fórmula de Stirling, he estado preguntando. Los matemáticos a menudo como para el uso de la regla de l'Hôpital, pero obviamente no pueden ser aplicadas al caso discreto inmediatamente (no significa teorema del valor). Si-como en este caso -, estás de suerte, podría encontrar agradable y bien estudiado las continuaciones en los reales.

Qué hacer en general? Hay una discreta versión relativa de la regla de l'Hôpital, tal vez usando diferencia de los cocientes?

Answer 1

Stolz–Cesàro parece ser lo que usted está buscando. Hay dos formas:

1.

Deje de $a_n$ y $b_n$ dos secuencias de acercarse $0$ como $n\to\infty$, con $b_n$ disminuyendo. A continuación,

$$\lim_{n\to\infty}\frac{a_n}{b_n}=\lim_{n\to\infty}\frac{a_{n+1}-a_n}{b_{n+1}-b_n}$$

si el segundo límite existe.

2.

Deje de $a_n$ y $b_n$ ser de dos secuencias, con $b_n$ ilimitados y en aumento. A continuación,

$$\lim_{n\to\infty}\frac{a_n}{b_n}=\lim_{n\to\infty}\frac{a_{n+1}-a_n}{b_{n+1}-b_n}$$

si el segundo límite existe.

Answer 2

La versión discreta de L'Hôspital de la regla, en mi opinión, es Abelian teoremas, incluyendo la L'Hôspital la regla de Silverman-Toeplitz teorema y su sepcial caso, Stolz-Cesàro teorema.

De de Bruijn es Asintótica de los métodos de análisis, se dice que

Un teorema de la cual se deriva asintótica información acerca de algún tipo de promedio de una función asintótica información acerca de la función de sí mismo, se llama Abelian teorema. Si se puede encontrar una condición adicional en virtud de la cual el recíproco de un Abelian teorema se mantiene, entonces esta condición es llamada una Tauberian condición, y a la inversa teorema se llama Tauberian teorema.

La cantidad que usted dio, como he intentado, no podía ser resuelto fácilmente con estos teoremas.

Deja $$a_n=\frac{4^n}{\binom{2n}n\sqrt n}$$ tenemos $$\ln a_{n+1}-\ln a_n=\frac12\ln(n+1)-\ln(n+\frac12)+\frac12\ln n=-\frac1{4n^2}+O\left(\frac1{n^3}\right)\tag1$$ Por lo tanto $\ln a_n$ converge como $n\to\infty$. Sin embargo, la anterior ecuación, el comportamiento asintótico de la diferencia, no es suficiente para determinar el valor límite, incluso si el resultado es refinado. Tales esfuerzos son generalmente un fracaso.

Sin embargo, si $S=\lim_{n\to\infty}\ln a_n$, podríamos determinar el comportamiento asintótico de $a_n-S$ a (1) fácilmente, ya que $\ln a_n=S-\sum_{k\ge n}(\ln a_k-\ln a_{k+1})$.

Comentario Uno podría determinar $S$ a través de la fórmula de Stirling. Hay otro enfoque, más elemental, creo que:

$$a_n^2=\left(\frac{(2n-1)!!}{(2n)!!}\right)^2(2n+1)\cdot\frac n{2n+1}\a\frac1\pi$$

por Wallis producto, por lo tanto $S=1/\sqrt\pi$.