¿Qué solución particular debo adivinar para esta relación?

Question

Sólo intento resolver una relación de recurrencia no homogénea:

$$f(n) = 2f(n-1) + n2^n$$

$$f(0) = 3$$

---

La ecuación característica es:

$$f(n) - 2f(n-1) = 0$$

$$a-2 = 0$$

$$a = 2$$

La solución homogénea es:

$$f_H(n) = b_0\cdot (2)^n$$

---

El lado derecho es:

$$n2^n$$

¿Cuál es la conjetura particular que debo hacer en base a esto?

Answer 1

(No se trata de una suposición, sino de una aproximación para encontrar la solución).

En primer lugar, reordenamos la relación dada para obtener:

$$f(n) - 2f(n-1) = n2^n$$

Dividir todo por $2^n$ . Esto nos da:

$$\frac{f(n)}{2^n} - \frac{f(n-1)}{2^{n-1}} = n$$

Haz una suma para explotar las posibles cancelaciones en el LHS:

$$\sum_{i = 1}^n\left(\frac{f(i)}{2^i} - \frac{f(i-1)}{2^{i-1}}\right) = \sum_{i = 1}^n i$$ $$\frac{f(n)}{2^n} - \frac{f(0)}{2^0} = \frac{n(n+1)}{2}$$ $$\frac{f(n)}{2^n} = \frac{n(n+1)}{2} + 3$$ $$f(n) = 2^{n-1}(n^2 + n + 6)$$

---

En general, si tienes cosas como $a_n - ka_{n-1} = b_n$ donde $k$ es una constante, dividiendo todo por $k^n$ puede ser una buena manera de empezar.

Answer 2

La respuesta de Yiyuan Lee es muy buena e inteligente.

De forma más general, tendrás que resolver la homogénea como lo hiciste y notar que $a = 2$ . Luego mira el lado derecho y observa que también es $2^n$ por lo que hay que buscar una solución de la forma : $$cn2^n$$ Sin embargo, este es el RHS así que añade un $n^2$ para intentar encontrar una solución de la forma : $$(c_1n^2 + c_2n)2^n$$ Sustituye esto en la ecuación y resuelve para $c_1$ y $c_2$ .

Answer 3

Sugerencia: resuélvelo en tres pasos.

1. Intenta algo como el RHS, digamos $an2^n$ .

2. Si es necesario, modifíquelo incluyendo términos de "orden inferior"; en este caso, cambie la conjetura por $(an+b)2^n$ .

3. Compara la solución homogénea, aquí $f_H(n)=A2^n$ . Si su suposición tiene algún término compartido con $f(n)$ multiplique la suposición por $n$ . Repita la operación hasta que no haya términos compartidos. En este caso $(an+b)2^n$ tiene el término $b2^n$ en común con $f_H(n)$ Así pues, modifique la conjetura a $(an^2+bn)2^n$ . Ahora no hay nada en común con $f_H(n)$ Así que este es el que hay que elegir.

Answer 4

He intentado calcular algunos valores y he encontrado esta fórmula:

$$f(n)=3\cdot2^n+\frac{n^2+n}22^n$$

Es fácil demostrarlo por inducción en $n$ .

Answer 5

Sólo hay que solucionar el problema utilizando funciones generadoras. Definir $F(z) = \sum_{n \ge 0} f(n) z^n$ , ajustar los índices para que no haya sustracciones: $$ f(n + 1) = 2 f(n) + (n + 1) 2^{n + 1} $$ Multiplicar por $z^n$ , suma sobre $n \ge 0$ reconocer: \begin{align} \sum_{n \ge 0} f(n + 1) z^n &= \frac{F(z) - f(0)}{z} \\ \sum_{n \ge 0} (2 z)^n &= \frac{1}{1 - 2 z} \\ \sum_{n \ge 0} n 2^n z^{n - 1} &= \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - 2 z} \\ \sum_{n \ge 0} (n + 1) 2^{n + 1} z^n &= \frac{2}{(1 - 2 z)^2} \end{align} Esto da: $$ \frac{F(z) - 3}{z} = 2 F(z) + \frac{2}{(1 - 2 z)^2} $$ Resolver para $F(z)$ como fracciones parciales: $$ F(z) = \frac{3}{1 - 2 z} - \frac{1}{(1 - 2 z)^2} + \frac{1}{(1 - 2 z)^3} $$ Utilizando el teorema del binomio generalizado: \begin{align} f(n) &= 3 \binom{-1}{n} (-2)^n - \binom{-2}{n} (-2)^n + \binom{-3}{n} (-2)^n \\ &= 3 \cdot 2^n - (n + 1) 2^n + \frac{(n + 2) (n + 1)}{2} 2^n \\ &= (n^2 + n + 6) \cdot 2^{n - 1} \end{align} A primera vista, esta comprobación, como $f(0) = 3$ .