КМ 7.7

[caxap]

Решить реккурентное соотношение (через произв. функцию)
$g_0=1$
$g_n=g_{n-1}+2g_{n-2}+...+ng_0, n > 0$.

Составил ПФ, но не сходится с ответом. Я умножил второе уравнение на $z^n$, проссуммировал по $n\ge 1$ и сложил с первым уравнением. Получилось

$$\sum_{n\ge 0} g_n z^n=1+\sum_{n\ge 1} \left( \sum_{k=0}^n k g_{n-k} \right) z^n$$

Слева --- $G(z)$, справа внутренняя сумма это свертка последовательности (1,2,3,..) (ПФ для нее $1/(1-z)^2$) с $G(z)$, то есть получается

$$G(z)=1+G(z)/(1-z)^2$$

А в ответе $G(z)=1+zG(z)/(1-z)^2$. Откуда взялся $z$ в числителе?

[RIP]

caxap в сообщении #337082 писал(а):

Откуда взялся $z$ в числителе?

$$\sum_{n=0}^\infty nz^n=\frac{z}{(1-z)^2}.$$

[caxap]

RIP
Ой, и правда. Я просто думал так: для последовательности (1,1,..) будет $1/(1-z)$, а для последовательности частичных сумм $1/(1-z)^2$. На компьютере проверил, оказывается $1/(1-z)^2$ смещена влево на 1 позицию.