Uzasadnienie wzoru rekurencyjnego

[WMP]

Jutro mam kolokwium i chcę przerobić zadania które mnie obowiązują, zatrzymałej sie jednak na:
Na ile sposobów można pomalować \(\displaystyle{ k}\) jednakowych kul mająć do dyspozycji \(\displaystyle{ n}\) kolorów? (\(\displaystyle{ n \in N, k \in N}\)).
Czyli mamy do czynienia z kombinacją z powtórzeniami.
c) Uzasadnić wzór rekurencyjny \(\displaystyle{ f(n,k) = f(n-1,k) + f(n,k-1)}\).
d) Uzasadnić, że \(\displaystyle{ f(n,k)}\) jest liczbą nieujemnych i całkowitoliczbowych rozwiązań równania: \(\displaystyle{ t_{1} + t_{2} + ... + t_{n} = k}\), gdzie \(\displaystyle{ t_{i} \ge 0}\) oznacza liczbę kul pomalowanych kolorem o numerze \(\displaystyle{ i = 1,2,...,n}\).
e) Niech \(\displaystyle{ f(x) = (1 + x + x^{2} + x^{3})^{3} = 1 + A_{1}x^{2} + A_{3}x^{3} + ... + A_{9}x^{9}}\). Jaki jest związek \(\displaystyle{ f(3,3)}\) z \(\displaystyle{ A_{3}}\)?
f) Niech \(\displaystyle{ f(x) = \frac{1}{1-x} = 1 + x + x^{2} + ..., x \in (-1,1)}\).
Jaką interpretację ma współczynnik przy k-tej potędze w rozwinięciu \(\displaystyle{ g(x) = (f(x))^{n}}\) ?

[lina2002]

c) Chcesz pomalować \(\displaystyle{ n}\) kul na \(\displaystyle{ k}\) kolorów. Możesz albo pomalować kule używając wyłącznie pierwszych \(\displaystyle{ n - 1}\) kolorów - stąd dostajesz składnik \(\displaystyle{ f(n - 1, k)}\) albo co najmniej jedną kulę na ostatni kolor i resztę dowolnie- stąd dostajesz składnik \(\displaystyle{ f(n, k - 1)}\)
d) Prosta odpowiedniość: \(\displaystyle{ t_i}\) - liczba kula pomalowana na \(\displaystyle{ i}\)-ty kolor.
f) Ten współczynnik jest równy \(\displaystyle{ f(n, k)}\) - zauważ, że żeby dostać \(\displaystyle{ x^k}\) wybieramy z każdego "nawiasu", czyli wyrażenia \(\displaystyle{ \frac{1}{1-x} = 1 + x + x^{2} + ...}\) (a jest ich \(\displaystyle{ n}\)) liczbę całkowitą i nieujemną. A to jest suma z podpunktu d).
(e) wynika z f))