Calcular buenos límites para $P(n) = n + nP(n-1)$

Question

¿Cuál es la técnica de cálculo de la siguiente recurrencia?

$$P(n) = n + nP(n-1)$$

(Suponemos que $P(1) = 1$ .)

Es evidente que el límite inferior de $P(n)$ es $n!$ y el límite superior es $(n+1)!$ que ya es una buena información. Sin embargo, me he preguntado si es posible mejorar esos límites o resolver la recurrencia exactamente.

Answer 1

No conozco ninguna solución exacta, pero una forma rápida de obtener un límite más preciso sería considerar la relación de $P(n)$ y $n!$ . Más concretamente, defina $$f(n)=\frac{P(n)}{n!}$$ y luego observar que satisface la relación de recurrencia $$f(n)=\frac{1}{(n-1)!}+f(n-1).$$ Esto se puede reescribir ventajosamente como $$f(n)=\sum_{i=0}^{n-1}\frac{1}{i!}$$ de donde podemos derivar fácilmente que $1\leq f(n)\leq \sum_{i=0}^{\infty}\frac{1}{i!}=e$ lo que da como resultado el límite

$$n!\leq P(n) \leq e\cdot n!.$$ Este es un límite razonablemente ajustado (que nos da la función dentro de un factor constante), y, como además tenemos que $\lim_{n\rightarrow\infty}\frac{P(n)}{n!}=e$ nos da una muy buena idea de la tasa de crecimiento de la función.

---

En realidad, considerando las dos expresiones $$n!\left(\frac{1}{0!}+\frac{1}{1!}+\ldots +\frac{1}{(n-1)!}\right)$$ y $$n!\left(\frac{1}{0!}+\frac{1}{1!}+\ldots +\frac{1}{(n-1)!}+\frac{1}{n!}+\frac{1}{(n+1)!}+\ldots\right)=n!\cdot e$$ encontramos que la diferencia es $$\frac{n!}{n!} + \frac{n!}{(n+1)!}+\frac{n!}{(n+2)!}+\ldots$$ que está entre $1$ y $2$ para $n\geq 1$ . Así, una forma cerrada es la siguiente: $$P(n)=\lfloor e\cdot n!\rfloor - 1$$ donde $\lfloor \cdot \rfloor$ es el función del suelo .

Answer 2

Esto no es una respuesta, pero probablemente sea demasiado largo para un comentario

Utilizando un CAS, si $P(1)=1$ la solución de la ecuación de recurrencia $$P_n = n + n\,P_{n-1}$$ viene dada por $$P_n=e\, n\, \Gamma (n,1)$$ donde aparece la función gamma incompleta y entonces $P_n<e\, n!$ .

De hecho, el valor de $P_n$ está muy cerca del límite superior ya que $P_4=64$ mientras que $4! e\approx 65.2388$ , $P_5=325$ mientras que $5! e\approx 326.194$ ,, $P_6=1956$ mientras que $6! e\approx 1957.16$ .

Según $OEIS$ (secuencia $A007526$ ) $P_n=\lfloor e n!-1\rfloor$ .

Answer 3

Aplicando un método estándar, si $P(n) = n + nP(n-1)$ , entonces $\frac{P(n)}{n!} = \frac1{(n-1)!} + \frac{P(n-1)}{(n-1)!}$ .

Dejemos que $Q(n) = \frac{P(n)}{n!}$ . Entonces $Q(n) =\frac1{(n-1)!}+Q(n-1)$ , o $Q(n)-Q(n-1) =\frac1{(n-1)!}$ .

Suma de $n=1$ a $m$ , $\sum_{n=1}^{m}(Q(n)-Q(n-1)) =\sum_{n=1}^{m}\frac1{(n-1)!}$ o $Q(m)-Q(0) =\sum_{n=0}^{m-1}\frac1{n!}$ .

Por lo tanto, $\frac{P(m)}{m!}-\frac{P(0)}{0!} =\sum_{n=0}^{m-1}\frac1{n!}$ o $P(m) =m!P(0)+m!\sum_{n=0}^{m-1}\frac1{n!}$ .

Desde $\sum_{n=0}^{m-1}\frac1{n!} \approx e$ , $P(m) =m!(P(0)+e)$ .

Answer 4

Mediante la generación de secuencias:

Dejemos que $g(x) = \sum_{n=1}^\infty P(n)x^n$ . Observamos que $$\sum_{n=2}^\infty nP(n-1)x^n = \\ \sum_{n=1}^\infty (n+1)P(n)x^{n+1} =\\ x \frac{d}{dx}\left(\sum_{n=1}^\infty P(n)x^{n+1} \right) =\\ x g'(x)$$ Ahora, por nuestra relación de recurrencia, tenemos $$P(n) - nP(n-1) = n \implies\\ \sum_{n=2}^\infty (P(n) - nP(n-1))x^n = \sum_{n=2}^\infty nx^n \implies\\ (g(x) - P(0)) - x\,g'(x) = - \frac{(x-2)x^2}{(x-1)^2} \implies\\ g'(x) - \frac 1x g(x) = \frac{(x-2)x^2}{(x-1)^2} - 1$$ Esta es una ecuación diferencial que se puede resolver para $g$ . Una vez que tenemos $g$ podemos encontrar la expansión de Taylor de $g$ centrado en $x = 0$ . Los coeficientes de esta expansión son la solución de nuestra relación de recurrencia.