temp-polynomials.tex

Завершим мы этот параграф двумя довольно отвлечёнными результатам, которые интересны нам скорее не сами по себе (хотя они имеют применения), а с точки зрения нового для нас вида доказательств, которые полезно иметь ввиду.

\begin{thm}
$${m+n \choose k} = \sum_{i=0}^k {m\choose i}{n\choose k-i}$$
\end{thm}
\begin{proof}
Используем разложение $(1+x)^{m+n}$ по теореме 3.26:
\begin{align*}
\sum_{k=0}^{m+n}{m+n \choose k}x^k & = (1+x)^{m+n} \\
& = (1+x)^m(1+x)^n \\
& = \left(\sum_{k=0}^m{m\choose k}x^k\right) \left(\sum_{i=0}^n {n\choose i}x^i\right) \\
& = \sum_{k=0}^m\sum_{i=0}^n{m\choose k}{n\choose i}x^{i+k} \\
& = \sum_{k=0}^{m+n} \left( \sum_{i=0}^k {m\choose i}{n\choose k-i} \right) x^k
\end{align*}
\end{proof}

\begin{thm}
$$\sum_{k=0}^n \fstirling{n}{k}x^k = x^{\lceil n \rceil}$$
где $x$ ~--- некоторая переменная.
\end{thm}
\begin{proof}
В левой и правой частях (после раскрытия всех скобок) стоят \term{многочлены}, то есть выражения вида
$$a_n x^n + a_{n-1}x^{n-1} + \ldots + a_{0}$$
Величины $\{a_i\}$ называются коэффициентами многочлена. Мы покажем, что слева и справа в утверждении теоремы эти коэффициенты совпадают. Пусть
$$x^{\lceil n \rceil} = \sum_{k=0}^n a_{n, k} x^k$$
Это же самое можно переписать следующим образом:
\begin{align*}
x^{\lceil n \rceil} &= (x+n-1)x^{\lceil n-1 \rceil} = (x+n-1)\sum_{k=0}^{n-1}a_{n-1, k}x^k \\
& = \sum_{k=1}^n a_{n-1, k-1} x^k + (n-1)\sum_{k=0}^{n-1}a_{n-1,k} x^k \\
& = a_{n-1,0} + a_{n-1, n-1}x^n + \sum_{k=1}^{n-1} (a_{n-1,k-1} + (n-1) a_{n-1, k})x^k
\end{align*}
Из последнего выражения мы видим, что
$$a_{n, k} = a_{n-1, k-1} + (n-1)a_{n-1, k}$$
то есть что коэффициенты при $x$ в выражении $x^{\lceil n \rceil}$ удовлетворяют тому же рекурсивному тождеству, которое позволяет нам вычислять числа Стирлинга (теорема~3.20). Осталось доказать, что начальные значения так же совпадают, но это очевидно: при раскрытии скобок для $x^{\lceil n \rceil}$ получаем в явном виде, что $a_{n, n} = 1$ и $a_{n, 0} = 0$, что завершает доказательство.
\end{proof}