Autor Tema: Resolución de recurrencias con funciones generatrices

0 Usuarios y 1 Visitante están viendo este tema.

19 Mayo, 2019, 06:03 pm
Leído 1087 veces

mss

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 39
  • Karma: +0/-0
  • Sexo: Femenino
Buenas tardes.
He estado repasando unos ejercicios acerca de resolución de recurrencias mediante funciones generatrices, y he encontrado la siguiente no homogénea, que lleva unos días dándome problemas:
\( a_n = a_{n-1} + 2n - 1 \) donde el término \( a_0 = 0 \) y \( a_1 = 1 \)

Lo primero que he hecho ha sido:
\( A(x) = 0 + x + \displaystyle\sum_{n=2}^\infty{} a_n * x^n  \), que sería lo mismo que:
\( A(x) = x + x *  \displaystyle\sum_{n=2}^\infty{}a_{n-1} * x^{n-1} + 2 * \displaystyle\sum_{n=2}^\infty{}n*x^n - \displaystyle\sum_{n=2}^\infty{}x^n \)

De aquí me surgen dos dudas. La primera sería si el -1 se escribe tal y como he señalado en la línea superior, con un sumatorio de \( x^n \); y la segunda, cómo se derivaría la parte de \( \displaystyle\sum_{n=2}^\infty{}n*x^n \).

Muchas gracias :)

20 Mayo, 2019, 10:26 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 48,994
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Buenas tardes.
He estado repasando unos ejercicios acerca de resolución de recurrencias mediante funciones generatrices, y he encontrado la siguiente no homogénea, que lleva unos días dándome problemas:
\( a_n = a_{n-1} + 2n - 1 \) donde el término \( a_0 = 0 \) y \( a_1 = 1 \)

Lo primero que he hecho ha sido:
\( A(x) = 0 + x + \displaystyle\sum_{n=2}^\infty{} a_n * x^n  \), que sería lo mismo que:
\( A(x) = x + x *  \displaystyle\sum_{n=2}^\infty{}a_{n-1} * x^{n-1} + 2 * \displaystyle\sum_{n=2}^\infty{}n*x^n - \displaystyle\sum_{n=2}^\infty{}x^n \)

De aquí me surgen dos dudas. La primera sería si el -1 se escribe tal y como he señalado en la línea superior, con un sumatorio de \( x^n \); y la segunda, cómo se derivaría la parte de \( \displaystyle\sum_{n=2}^\infty{}n*x^n \).

Muchas gracias :)

No está mal lo que has hecho, pero lo puedes dejar así:

\( A(x)=x+x\displaystyle\sum_{n=2}^\infty{}a_{n-1}x^{n-2}+\displaystyle\sum_{n=2}^\infty(2n-1)x^n=x+x\displaystyle\sum_{n=1}^\infty{}a_{n}x^{n}+\displaystyle\sum_{n=2}^\infty(2n-1)x^n=xA(x)+\displaystyle\sum_{n=1}^\infty(2n-1)x^n \)

De donde:

\( A(x)=\dfrac{1}{1-x}\left(\displaystyle\sum_{n=1}^\infty(2n-1)x^n\right)=\left(\displaystyle\sum_{n=0}^\infty{}x^n\right)\left(\displaystyle\sum_{n=1}^\infty(2n-1)x^n\right)=\displaystyle\sum_{k=0}^\infty{}a_k \)

y asi:

\( a_n=\displaystyle\sum_{i=1}^n{}(2i-1)=2\displaystyle\sum_{i=1}^ni-n=2\cdot \dfrac{n(n+1)}{2}-n=n^2 \)

Saludos.

07 Junio, 2019, 07:04 pm
Respuesta #2

mss

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 39
  • Karma: +0/-0
  • Sexo: Femenino

07 Junio, 2019, 09:05 pm
Respuesta #3

Masacroso

  • Moderador Global
  • Mensajes: 2,583
  • País: es
  • Karma: +0/-0
En estos casos vale la pena desplazar los índices de la recurrencia para que el menor término sea \( a_n \), es decir, en vez de usar \( a_n=a_{n-1}+2n-1 \) los cálculos son ligeramente más simples usando la recurrencia equivalente \( a_{n+1}=a_n+2(n+1)-1=a_n+2n+1 \), y definiendo \( A(x):=\sum_{n\ge 0}a_n x^n \) entonces nos queda por un lado

\( \displaystyle \sum_{n\ge 0}a_{n+1}x^n=x^{-1}(A(x)-a_0)=x^{-1}A(x) \)

y por el otro

\( \displaystyle {\sum_{n\ge 0}a_nx^n+2\sum_{n\ge 0} nx^n+\sum_{n\ge 0}x^n
=A(x)+2x D\sum_{n\ge 0}x^n+\frac1{1-x}\\
=A(x)+\frac{2x}{(1-x)^2}+\frac1{1-x}=A(x)+\frac{1+x}{(1-x)^2}} \)

donde la \( D \) es el operador derivada (respecto de \( x \)). Y luego despejando nos queda

\( \displaystyle {A(x)=\frac{x(1+x)}{(1-x)^3}=(x+x^2)\sum_{n\ge 0}\binom{-3}{n}(-1)^nx^n=(x+x^2)\sum_{n\ge 0}\binom{n+2}{2}x^n\\
=\sum_{n\ge 0}\left(\binom{n+1}2+\binom{n}2\right)x^n=\frac12\sum_{n\ge 0}((n+1)n+n(n-1)) x^n=\sum_{n\ge 0}n^2 x^n} \)



En general se puede demostrar que, dado un polinomio cualquiera \( p(n):=\sum_{k=0}^m c_k n^k \) entonces

\( \displaystyle \sum_{n\ge 0} p(n) x^n=p(xD)\sum_{n\ge 0}x^n=p(xD)\frac1{1-x} \)

con \( p(xD)=\sum_{k=0}^m c_k (xD)^k \) donde \( c_k (xD)^k \) significa "derivar y después multiplicar por \( x \), \( k \)-veces consecutivas, y después multiplicar por \( c_k \)".



En este caso otra forma de resolver la recurrencia también sería definir \( \Delta a_n:=a_{n+1}-a_n \), entonces tenemos la recurrencia \( \Delta a_n=2n+1 \), y como \( \sum_{n=0}^{m-1}\Delta a_n=a_m-a_0=a_m \), entonces \( a_m=\sum_{n=0}^{m-1}(2n+1)=m(m-1)+m=m^2 \).

CORREGIDO: había un error en la definición del operador diferencial, originalmente había puesto \( p(D) \) pero en verdad es \( p(xD) \).