Dowód, liczby Stirlinga

[Kvothe]

Witam, chcę udowodnić, że:

\(\displaystyle{ x^n = \sum_k^n \left\{
\begin{matrix}
n\\
k
\end{matrix}
\right\} x^{\underline{k}}}\)

Dla \(\displaystyle{ n_0 = 1}\) wychodzi, problem przy \(\displaystyle{ n+1}\):

\(\displaystyle{ x^{n+1} = \sum_k^{n+1} \left\{
\begin{matrix}
n+1\\
k\\
\end{matrix}
\right\}x^{\underline{k}}}\)

Próbowałem korzystać z:

\(\displaystyle{ \left\{
\begin{matrix}
n\\
k\\
\end{matrix}
\right\} =k\cdot\left\{
\begin{matrix}
n-1\\
k\\
\end{matrix}
\right\} +\left\{
\begin{matrix}
n-1\\
k-1\\
\end{matrix}
\right\}}\)

I mam:

\(\displaystyle{ x^{n+1} = \sum_k^{n+1}\left(k\cdot \left\{
\begin{matrix}
n\\
k\\
\end{matrix}
\right\} + \left\{
\begin{matrix}
n\\
k-1\\
\end{matrix}
\right\} \right) x^{\underline{k}}}\)

Wskazówka?

[Qń]

\(\displaystyle{ x^n = \sum_k^n \left\{
\begin{matrix}
n\\
k
\end{matrix}
\right\} x^{\underline{k}}}\)

Skąd wziąłeś taką konwencję zapisu? Przecież to zupełnie bez sensu, bo nie wiadomo jaki jest zakres sumowania. Powszechnie przyjęte konwencje to na przykład:
\(\displaystyle{ \sum_{k=0}^na_k}\) (sumowanie po całkowitych \(\displaystyle{ k}\) od \(\displaystyle{ 0}\) do \(\displaystyle{ n}\))
oraz
\(\displaystyle{ \sum_{k}a_k}\) (sumowanie po wszystkich \(\displaystyle{ k}\) całkowitych)

Proponuję zacząć od wybrania którejś z sensownych konwencji.

Q.

[Kvothe]

Tam miała być ta druga konwencja.

[Qń]

Po pierwsze - wypadałoby zatem zapisać prawidłowo co masz udowodnić:
\(\displaystyle{ x^n = \sum_k \left\{ \begin{matrix} n\\ k \end{matrix} \right\} x^{\underline{k}}}\)
a teza indukcyjna to:
\(\displaystyle{ x^{n+1} = \sum_k \left\{ \begin{matrix} n+1\\ k \end{matrix} \right\} x^{\underline{k}}}\)

Po drugie - przekształcanie tezy w dowodzie indukcyjnym jest formalnie poprawne, ale zazwyczaj nieeleganckie. Elegancko jest wyjść od jednej strony tej tezy i pokazać, że jest równa drugiej stronie.

Po trzecie - skoro zacząłeś od przekształcenia prawej strony, to mamy na razie:
\(\displaystyle{ P= \sum_k\left(k\cdot \left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\} + \left\{ \begin{matrix} n\\ k-1\\ \end{matrix} \right\} \right) x^{\underline{k}}}\)
Rozbij teraz to na dwie sumy i w drugiej sumie przesuń wskaźnik sumowania tak, żeby w obu sumach była liczba Stirlinga \(\displaystyle{ \left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\}}\) (z \(\displaystyle{ k}\) w dolnym indeksie). Następnie z powrotem zwiń dwie sumy w jedną i zastanów się jak uprościć wyrażenie z dolnymi silniami, które pojawi się wewnątrz sumy.

Q.

[Kvothe]

Zatem:

\(\displaystyle{ P= \sum_k\left(k\cdot \left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\} + \left\{ \begin{matrix} n\\ k-1\\ \end{matrix} \right\} \right) x^{\underline{k}} =\sum_k\left(k\cdot \left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\}\cdot x^{\underline{k}}\right) +\sum_k\left(\left\{ \begin{matrix} n\\ k-1\\ \end{matrix} \right\}\cdot x^{\underline{k}}\right) =\sum_k\left(k\cdot \left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\}\cdot x^{\underline{k}}\right) +\sum_{k+1}\left(\left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\}\cdot x^{\underline{k+1}}\right) = \sum_k\left(k\cdot \left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\}\cdot x^{\underline{k}}+\left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\}\cdot x^{\underline{k+1}} \right) = \sum_k \left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\} \left( k \cdot x^{\underline{k}}+ x^{\underline{k+1}} \right) = \sum_k \left( \left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\} \cdot x \cdot x^{\underline{k}}\right)}\)

I teraz skoro \(\displaystyle{ x}\) nie zależy od parametru po którym następuje sumowanie, to można wyłączyć przed sumę:

\(\displaystyle{ P = x \sum_k \left( \left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\} \cdot x^{\underline{k}}\right)}\)

Teraz z założenia:

\(\displaystyle{ P = x \cdot x^n = x^{n+1}}\)

Czy można sobie tak zwijać sumy o różnych indeksach, czy był to przypadek szczególny? Rozumiem, że:

\(\displaystyle{ \sum_k \left\{ \begin{matrix} n\\ k-1\\ \end{matrix} \right\} = \sum_{k+1} \left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\}}\)

ale ta pierwsza suma po "przesuniętych" indeksach sumuje.

[Qń]

Wszystko się zgadza.

Rozumiem, że:
\(\displaystyle{ \sum_k \left\{ \begin{matrix} n\\ k-1\\ \end{matrix} \right\} = \sum_{k+1} \left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\}}\)

To prawda, ale ładniej jest tę prawdę zapisać jako:
\(\displaystyle{ \sum_k \left\{ \begin{matrix} n\\ k-1\\ \end{matrix} \right\} = \sum_{k} \left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\}}\)
Jeśli bowiem sumujemy po wszystkich liczbach całkowitych \(\displaystyle{ k}\), to wszystko jedno czy wewnątrz sumy będzie \(\displaystyle{ k}\), \(\displaystyle{ k+1}\) czy też \(\displaystyle{ k+112423453245}\) - w każdym wypadku i tak wysumujemy po wszystkich liczbach całkowitych.

Q.

[Kvothe]

Teraz jasne, dzięki.