Udowodnic nierownosc dla rownania rekurencyjnego

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
wika116
Użytkownik
Użytkownik
Posty: 22
Rejestracja: 1 mar 2011, o 22:28
Płeć: Kobieta
Lokalizacja: poland
Podziękował: 4 razy

Udowodnic nierownosc dla rownania rekurencyjnego

Post autor: wika116 »

Hej,
mam nastepujace rownanie rekurencyjne
\(\displaystyle{ g_{0} = 1, n \cdot g _{n} = \sum_{0 \le k < n}^{} \frac{ g_{k} }{n - k}}\)
Chce udowodnic, ze
\(\displaystyle{ 0< g_{n} \le 1.}\)
Czy ma ktos pomysl jak to zrobic najprosciej? Probuje przez indukcje, ale jakos nie moge dojsc do rozwiazania. Z gory dzieki
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Udowodnic nierownosc dla rownania rekurencyjnego

Post autor: Premislav »

Indukcyjnie łatwo wykazać, że \(\displaystyle{ g_n>0}\). Mianowicie dla \(\displaystyle{ n=0}\) założenia zadania załatwiają sprawę, a zakładając, że dla pewnego \(\displaystyle{ n\in \NN^+}\) i wszystkich \(\displaystyle{ k}\) mniejszych od \(\displaystyle{ n}\) jest \(\displaystyle{ g_k>0}\) mamy
\(\displaystyle{ g_n=\frac 1 n\sum_{0 \le k < n}^{} \frac{ g_{k} }{n - k}=\\=\sum_{0 \le k < n}^{} \frac{ g_{k} }{n^2 - kn}>0,}\)
ponieważ \(\displaystyle{ n^2-kn>0}\) dla \(\displaystyle{ k=0,\ldots n-1}\), a także iloraz liczb dodatnich jest dodatni i suma liczb dodatnich jest dodatnia.
A tak można oszacować \(\displaystyle{ g_n}\) z góry: skoro już pokazaliśmy, że wyrazy tego ciągu są dodatnie, to
zauważmy, że dla \(\displaystyle{ k=0,\ldots n-1}\) (gdzie \(\displaystyle{ n\in \NN^+}\)) jest
\(\displaystyle{ \frac{g_k}{n-k}\le \frac{\max\left\{ g_1, \ldots g_{n-1}\right\} }{n-(n-1)}=\\=\max\left\{ g_1, \ldots g_{n-1}\right\},}\)
czyli mamy
\(\displaystyle{ ng_n= \sum_{k=0}^{n-1} \frac{ g_{k} }{n - k}\le n \max\left\{ g_1, \ldots g_{n-1}\right\}}\)
a więc \(\displaystyle{ g_n \le \max\left\{ g_1, \ldots g_{n-1}\right\}}\)
i to załatwia krok indukcyjny przy użyciu indukcji zupełnej.
ODPOWIEDZ