Cómo resolver a esta relación de recurrencia

Question

¿Cuáles son algunas maneras para resolver esta relación de recurrencia:

$a(n+1)=2 a(n) - a(n-1) -1, \text{ with }a(0)=0, a(10)=0?$

Traté de convertir esta ecuación no homogénea en un homogénea uno de los siguientes Wikipedia:

$b_{n}=Ab_{n-1}+Bb_{n-2}+K \,$ puede ser convertida en forma homogénea como de la siguiente manera: El estado de equilibrio se encuentra por establecimiento $b_n = b_{n−1} = b_{n−2} = b^{*}$ a obtenga $b^{*} = \frac{K}{1-A-B}. \, $. El no-homogénea de la recurrencia de la puede escribirse en forma homogénea como $[b_n -b^{*}]=A[b_{n-1}-b^{*}]+B[b_{n-2}-b^{*}], \, $

Pero en la relación de recurrencia dada al principio de este post, el denominador en $b^{*} = \frac{K}{1-A-B} \, $$1-2+1=0$. Entonces, ¿cómo puedo resolver la relación de recurrencia? Gracias de antemano!

PS: hay algunos libros o sitios de internet con algunos resumen de varias maneras para resolver la recurrencia de la relación?

Answer 1

María: Usted puede considerar la ecuación de $n+2$ en lugar de $n+1$; esto nos da $$ a(n+2)=2a(n+1)-a(n)-1.$$ Subtract the first equation from this one. We obtain $$\begin{array}{rl}a(n+2)-a(n+1)&=(2a(n+1)-a(n)-1)-(2a(n)-a(n-1)-1)\\&=2a(n+1)-3a(n)+a(n-1),\end{array}$$ or $$a(n+2)=3a(n+1)-3a(n)+a(n-1).$$

En general, si la ecuación es "casi homogénea", sino por una constante, el mismo truco de restar consecutivos instancias de la recurrencia nos da una ecuación homogénea.

La ecuación característica asociada es ahora $x^3-3x^2+3x-1=0$ o $(x-1)^3=0$. Esto significa que $a(n)=A+Bn+Cn^2$ para algunas constantes $A,B,C$.

En general, si la ecuación tiene la forma $(x-r)^k(x-b)^s\dots=0$, entonces la solución general tendrá la forma $$a(n)=(A+Bn+\dots+C n^{k-1})r^n+(D+En+\dots+F n^{s-1})b^n+\dots$$ (en el más estudiado caso, la característica de la ecuación no tiene raíces repetidas, pero como en tu ejemplo, repite raíces puede ocurrir, así que tenemos esta versión más general).

Para encontrar $A,B,C$ en nuestra ecuación para $a(n)=A+Bn+Cn^2$, podemos utilizar el dado de condiciones iniciales. Está seguro de la condición de $a(10)=0$ es correcta, en lugar de $a(1)=0$?

Con $a(1)=0$,$0=A+B+C$. También, $a(0)=0$, lo $A=0$. Finalmente, $a(2)=2a(1)-a(0)-1=-1$, con el original de la recurrencia, por lo $A+2B+4C=-1$. Esta facilidad que nos da $A=0$, $B=1/2$, y $C=-1/2$ o $$ a(n)=\frac{n-n^2}2. $$

Tenga en cuenta que necesitábamos para calcular $a(2)$ antes de que pudiéramos encontrar $A,B,C$. Esto es debido a que la ecuación original no fue homogénea, de manera que aunque es de segundo orden, se necesita un adicional de un estado inicial a los dos nos da. (Nota de la homogénea de la ecuación que se obtiene es de tercer orden, se necesitan 3 condiciones iniciales.)

---

Por desgracia, yo no sé, de una manera decente de referencia en las relaciones de recurrencia en un nivel elemental (yo sé de uno, en español, una traducción de un pequeño ruso folleto publicado por Mir eds. años atrás). Hay varios métodos estándar que podría no ser tan elemental como usted quiera, pero usted puede disfrutar viendo todos modos: el Uso de álgebra lineal o funciones de generación. Por último, una buena referencia es "generatingfunctionology",

http://www.math.upenn.edu/~wilf/DownldGF.html

y para el ex una buena referencia es el Volumen II de Apostol de Cálculo del libro.

---

Hmm... Con $a(10)=0$, podemos proceder de la siguiente manera: Tenemos $$a(n)=A+Bn+Cn^2$$ and so $$A=0$$ (since $un(0)=0$) and $$10B+100C=0$$ (since $un(10)=0$ and $Un=0$). We also have $$a(n+2)=2a(n+1)-a(n)-1,$$ o $$ B(n+2)+C(n+2)^2=2B(n+1)+2C(n+1)^2-Bn-Cn^2-1, $$ which simplifies to $2C=-1$, or $$C=-1/2.$$ Then $$B=5,$$ from the equation for $un(10)=0$, and $$ a(n)=5n-\frac{n^2}2. $$

Answer 2

Usted obtener todas las soluciones de la ecuación no homogénea por encontrar alguna solución específica de la ecuación no homogénea y agregar a todas las soluciones de la ecuación homogénea. El estado estacionario ansatz es una manera de encontrar una solución de la ecuación no homogénea, pero si no funciona, como en este caso, usted puede continuar con el enfoque general de la primera búsqueda de una solución específica para la ecuación no homogénea. A continuación, la Wikipedia sección citado muestra cómo encontrar toda la homogeneidad de las soluciones que usted necesita para agregar a ella.

En el presente caso, también hay otra solución: puede reescribir su recurrencia relación como

$$a(n+1)-2a(n)+a(n-1)=-1\;.$$

De esta forma, usted puede ver que el lado izquierdo es una doble diferencia: la Definición de

$$(\Delta b) (n) := b (n+1) - b(n)\;,$$

podemos escribir la ecuación como

$$(\Delta\Delta a)(n-1) = -1\;.$$

Esto lo podemos resolver por dos veces con el hecho de que "la inversa de a$\Delta$$\Sigma$":

$$(\Delta a)(n-1) = -n + c\;,$$ $$a(n-1)= -\frac{n(n+1)}{2}+cn+d$$

con "constantes de la suma de" $c$ $d$ que se puede determinar para satisfacer las condiciones iniciales. La determinación de las constantes será más fácil si usted reescribir esto como

$$a(n)=-n^2/2+c'n+d'$$

con nuevas constantes $c'$, $d'$.

Answer 3

Funciones de generación para el rescate. Definir $A(z) = \sum_{n \ge 0} a(n) z^n$, multiplicar el pasado 2 de recurrencia por $z^n$ y suma más de $n \ge 0$. Reconociendo: \begin{align} \sum_{n \ge 0} a(n + 1) z^n &= \frac{A(z) - a(0)}{z} \\ \sum_{n \ge 0} a(n + 2) z^n &= \frac{A(z) - a(0) - a(1) z}{z^2} \\ \sum_{n \ge 0} z^n &= \frac{1}{1 -z} \end{align} da, mediante el desconocido $a(1)$: $$ \frac{A(z) - a(1) z}{z^2} = 2 \frac{A(z)}{z} (z) - \frac{1}{1 - z} $$ A partir de esta maxima se obtiene la fracción parcial de expansión: $$ A(z) = - \frac{1 + a(1)}{1 - z} + \frac{2 + a(1)}{(1 - z)^2} - \frac{1}{(1 - z)^3} $$ A partir de aquí, el uso de la generalizada del teorema del binomio: $$ a(n) = - (1 + a(1)) + (n + 1)(2 + a(1)) - \frac{(n + 1) (n + 2)}{2} = - \frac{n^2 - (2(1) + 1) n}{2} $$ Como $a(10) = 0$, esto le da a $a(1) = 9 / 2$, y por lo tanto: $$ a(n) = \frac{n (10 - n)}{2} $$