Udownodnij równoważność poniższego wzoru z podstawową definicją liczb Catalana
\(\displaystyle{
\begin{cases}
c_n= \frac{4n-2}{n+1}c_{n-1}, \qquad n \ge 1 \\
c_0=1
\end{cases}
}\)
Podstawowa definicja liczb Catalana
\(\displaystyle{
c_n= \frac{1}{n+1} {2n \choose n} = \frac{(2n)!}{(n+1)!n!} , \qquad n=0,1,2,...
}\)
Proszę o pomoc
dowód wzoru rekurencyjnego
-
- Użytkownik
- Posty: 19
- Rejestracja: 30 sie 2017, o 17:22
- Płeć: Kobieta
- Lokalizacja: Łowicz
- Podziękował: 9 razy
- Janusz Tracz
- Użytkownik
- Posty: 4065
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1392 razy
Re: dowód wzoru rekurencyjnego
Ze wzoru rekurencyjnego wynika:
\(\displaystyle{ \frac{c_n}{c_{n-1}} = \frac{4n-2}{n+1}}\)
podstaw pod ten wzór
\(\displaystyle{ c_n= \frac{1}{n+1} {2n \choose n} = \frac{(2n)!}{(n+1)!n!}}\)
oraz
\(\displaystyle{ c_{n-1}= \frac{1}{n} {{2(n-1) \choose (n-1)}} = ...}\)
i sprawdź czy faktycznie spełniona jest równość. Na koniec trzeba jeszcze sprawdzić czy \(\displaystyle{ c_0=1}\) tak jak w rekurencji. Zasada indukcji matematycznej zakończy dowodów.
\(\displaystyle{ \frac{c_n}{c_{n-1}} = \frac{4n-2}{n+1}}\)
podstaw pod ten wzór
\(\displaystyle{ c_n= \frac{1}{n+1} {2n \choose n} = \frac{(2n)!}{(n+1)!n!}}\)
oraz
\(\displaystyle{ c_{n-1}= \frac{1}{n} {{2(n-1) \choose (n-1)}} = ...}\)
i sprawdź czy faktycznie spełniona jest równość. Na koniec trzeba jeszcze sprawdzić czy \(\displaystyle{ c_0=1}\) tak jak w rekurencji. Zasada indukcji matematycznej zakończy dowodów.