tablica z liczbami

[Czeczot]

Proszę o pomoc z takim zadaniem

\(\displaystyle{ \begin{tabular}{rcl}

1 & 1 & 1 ... \\
. & . & . ...

\end{tabular}}\)

wiersze tablicy numerowane są od góry do dołu rosnąco
wyrazy w danym wierszu numerowane są od lewej do prawej rosnąco

w pierwszym wierszu tej nieskończonej tablicy są same jedynki, a pozostałe miejsca otrzymuje się zgodnie z następującą zasadą:

\(\displaystyle{ k}\) - ty wyraz \(\displaystyle{ n}\) - tego wiersza (oznaczany dalej przez \(\displaystyle{ a_{kn}}\)) jest sumą \(\displaystyle{ k}\) pierwszych wyrazów z wiersza \(\displaystyle{ n-1}\)

Znaleźć \(\displaystyle{ a_{kn}}\)

[Qń]

Obliczenie wartości \(\displaystyle{ a_{kn}}\) dla małych \(\displaystyle{ n,k}\) łatwo prowadzi do hipotezy, że \(\displaystyle{ a_{kn}= \binom{n+k-2}{k-1}}\), którą można udowodnić indukcyjnie na przykład po \(\displaystyle{ n}\).

Q.

[Czeczot]

dzięki, próbuję tak

\(\displaystyle{ n=1 \Rightarrow a_{k1}=\binom{k-1}{k-1}=1}\), a to jest zgodne z określeniem tablicy

chcę udowodnić, że \(\displaystyle{ a_{kn}= \binom{n+k-2}{k-1} \Rightarrow a_{k(n+1)}= \binom{(n+1)+k-2}{k-1}}\)

i teraz miałbym pokazać, że \(\displaystyle{ \binom{(n+1)+k-2}{k-1}=a_{k(n+1)}=a_{1n}+....+a_{kn}=\binom{n+1-2}{1-1}+...+\binom{n+k-2}{k-1}}\)

i tu mam problem - jak udowodnić, że \(\displaystyle{ \binom{(n+1)+k-2}{k-1}=\binom{n+1-2}{1-1}+...+\binom{n+k-2}{k-1}}\)? osobno indukcją?

[Qń]

Wystarczy skorzystać ze znanej tożsamości:
\(\displaystyle{ \sum_{k=0}^n \binom{m+k}{k} = \binom{m+n+1}{n}}\)
(którą istotnie łatwo udowodnić indukcyjnie).

Alternatywną metodą na rozwiązanie zadania jest zauważenie, że wyrazy tablicy można zadać rekurencyjnie:
\(\displaystyle{ \begin{cases} a_{1n} = 1 \\ a_{k1} = 1\\ a_{kn} = a_{k-1, n} + a_{k,n-1}\end{cases}}\)
a dokładnie taką samą rekurencję spełnia \(\displaystyle{ \binom{n+k-2}{k-1}}\), a stąd wniosek, że \(\displaystyle{ a_{kn}=\binom{n+k-2}{k-1}}\).

Q.

[Czeczot]

dzięki, ale wystarczy pokazać, że \(\displaystyle{ \binom{n+k-2}{k-1}}\) spełnia rekurencję czy trzeba jeszcze pokazać, że nie ma innych rozwiązań tej rekurencji?

[Qń]

To że nie ma innych rozwiązań tej rekurencji widać chyba gołym okiem, bo ta rekurencja daje jednoznaczny "przepis" na policzenie dowolnego wyrazu \(\displaystyle{ a_{kn}}\).

Q.

[Czeczot]

no tak, dzięki raz jeszcze