Автор Тема: Решить рекуррентное соотношение с помощью производящих функций  (Прочитано 760 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Cityeh

  • Пользователь
  • Сообщений: 7
    • Просмотр профиля
Используя производящие функции, решить следующее рекуррентное соотношение: \(  \large a_n=-4a_{n-1}-4 a_{n-2}, \ a_0=1, \ a_1=-8 \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5048
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Пусть \(  \large G(x)=\sum\limits_{n=0}^{\infty} a_n x^n \) - искомая производящая функция. Имеем:

\(  \large a_0=1 \),

\(  \large a_1=-8 \),

\(  \large a_n=-4 a_{n-1}-4 a_{n-2}, \ n \ge 2 \).

Умножим первую строку на \(  \large x^0=1  \), вторую - на \(  \large x^1  \), а последнюю - на \(  \large x^n \):

\(  \large 1 \cdot a_0= 1 \cdot 1 \),

\(  \large a_1 \cdot x=-8 \cdot x \),

\(  \large a_n x^n=-4 a_{n-1}x^n-4 a_{n-2}x^n, \ n \ge 2 \).

Суммируя от нуля до бесконечности, получим:

\(  \large a_0+a_1x + \sum\limits_{n=2}^{\infty} a_n x^n =1-8x -4 \sum\limits_{n=2}^{\infty}a_{n-1}x^n - 4 \sum\limits_{n=2}^{\infty}a_{n-2}x^n  \),

что равносильно

\(  \large G(x) =1-8x -4 \sum\limits_{n=2}^{\infty}a_{n-1}x^n - 4 \sum\limits_{n=2}^{\infty}a_{n-2}x^n  \).

Займёмся тождественными преобразованиями рядов \(  \large \sum\limits_{n=2}^{\infty}a_{n-1}x^n \) и \(  \large \sum\limits_{n=2}^{\infty}a_{n-2}x^n  \). Имеем:

а) \(  \large \sum\limits_{n=2}^{\infty} a_{n-1} x^n=x \sum\limits_{n=2}^{\infty} a_{n-1} x^{n-1}=x \sum\limits_{n=1}^{\infty} a_{n} x^n=x \left(  \sum\limits_{n=1}^{\infty} a_{n} x^n +a_0-a_0 \right)=x \sum\limits_{n=0}^{\infty} a_{n} x^n - xa_0=xG(x) - x \);

б) \(  \large \sum\limits_{n=2}^{\infty}a_{n-2}x^n =x^2 \sum\limits_{n=2}^{\infty}a_{n-2}x^{n-2}=x^2 \sum\limits_{n=0}^{\infty}a_{n}x^{n}=x^2 G(x) \).

Итак, получили уравнение для нахождения производящей функции:

\(  \large G(x)=1-8x-4x G(x) + 4x - 4x^2 G(x) \ \Leftrightarrow \ G(x) = \frac{1-4x}{(2x+1)^2} \).

Разложим дробь \(  \large \frac{1-4x}{(2x+1)^2} \) на сумму простейших:

\(  \large \frac{1-4x}{(2x+1)^2}=\frac{a}{2x+1}+ \frac{b}{(2x+1)^2}=\frac{2ax + (a+b)}{(2x+1)^2}  \).

Сравнивая коэффициенты числителей первой и последней дробей, получим систему линейных алгебраических уравнений:

\(  \large \begin{cases} a+b=1 \\ 2a=-4 \end{cases} \ \Leftrightarrow \begin{cases} a=-2 \\ b=3 \end{cases} \).

Следовательно,

\(   \large \frac{1-4x}{(2x+1)^2}=\frac{-2}{2x+1}+ \frac{3}{(2x+1)^2}  \).

Значит,

\(  \large G(x)=\frac{-2}{1-(-2x)}+ \frac{3}{(1-(-2x))^2} =-2 \sum\limits_{n=0}^{\infty} (-2)^n x^n+3 \sum \limits_{n=0}^{\infty} (n+1)(-2)^n x^n=\sum\limits_{n=0}^{\infty} (-2)^n (3n+1)x^n \),

поскольку

\(  \large \sum\limits_{n=0}^{\infty}x^n=\frac{1}{1-x}, \  \sum\limits_{n=0}^{\infty}(n+1) x^n=\frac{1}{(1-x)^2} \).

Итак, \(  \large a_n=(-2)^n (3n+1) \) - последовательность, являющаяся решением рекуррентного соотношения.
 
Сказали спасибо: Байт, ZikWall