Resolviendo la ecuación recursiva$T(n) = 1 + \frac{2}{n} \sum_{i=1}^{n-2}T(i)$

Question

Tengo la ecuación recursiva $$ T (n) = \begin{cases} 0 & \text{for } n = 0,\\ 1 & \text{for } 0 < n \leq 2,\\ \displaystyle 1 + \frac{2}{n} \sum_{i=1}^{n-2} T(i) &\text{else.} \end {cases} $$

Ahora quiero resolverlo para grandes$n$.

Experimentalmente, podría determinar$\lim_{n \to \infty} T(n)/n \approx 0.4324314$, pero ¿hay una prueba sistemática para eso?

// EDITAR: Resultado experimental corregido. En mi cálculo, una constante se había deslizado hacia arriba en el nominador, lo siento.

Answer 1

Le sugiero que considere la función de generación$f(t) = \sum_{n=0}^{\infty}T(n)t^n$. Entonces, uno puede probar por la definición de$T(n)$ que$$\frac{\mathrm{d}}{\mathrm{d}t}f(t) = \frac{2t}{1-t} f(t) + \frac{1}{(1-t)^2}$$ with the initial condition $ f (0) = 0 $.

Esta ecuación diferencial tiene una solución$$f(t) = \frac{1-e^{-2t}}{2(1-t)^2} = \mbox{tedious computations}= \sum_{n=1}^{\infty} \left( \sum_{k=1}^n \frac{(n+1-k)}{k!}(-2)^{k-1} \right) t^n$ $ para que$$T(n)=\sum_{k=1}^n \frac{(n+1-k)}{k!}(-2)^{k-1}$ $

PD: Gracias a Christian Blatter, quien pacientemente revisó y corrigió mis cálculos. Si uno considera grandes$n$, puede aproximarse a$T(n)$ con

$$\sum_{k=1}^{\infty} \frac{(n+1-k)}{k!}(-2)^{k-1} = \frac{n+1}{-2} \sum_{k=1}^{\infty} \frac{1}{k!}(-2)^{k} - \sum_{k=1}^{\infty} \frac{k}{k!}(-2)^{k-1} = \frac{1-e^{-2}}{2} (n+1) - e^{-2}$ $ para que$$\lim_{n \to + \infty} \frac{T(n)}{n} = \frac{1-e^{-2}}{2}$ $