Rekurencja na przykładzie matmy dyskretnej

[hutsalo]

Mam pewien problem. Mianowicie poznaje definicje rekurencyjną od strony matematycznej. Mianowicie jak to zrozumieć? Jak obliczyć?
zwykle chodzi o ciąg \(\displaystyle{ a_{0}, a_{1}}\) itd. - dla którego przepis na element \(\displaystyle{ a_{n}}\) wykorzystuje jakieś poprzednie elementy \(\displaystyle{ a_{n-1}, a_{n-2}}\). Przepraszam jeśli umieściłem pytanie w złym dziale tematycznym. Proszę o przekierowanie.

[janusz47]

Forum nie prowadzi wykładów. Prosimy o konkretny przykład i własne przemyślenia związane z tym przykładem.

[Jan Kraszewski]

Mianowicie jak to zrozumieć?

Rekurencyjnie konstruujemy ciągi. Polega to na tym, że skonstruowanie każdego kolejnego wyrazu ciągu wymaga znajomości wcześniej skonstruowanych wyrazów tego ciągu. Tym różni się ona od definicji ciągu jawnym wzorem - tam żeby wyznaczyć \(\displaystyle{ a_{1000}}\) wystarczy, że wstawisz \(\displaystyle{ 1000}\) do tego jawnego wzoru. W wypadku ciągu zdefiniowanego rekurencyjnie, żeby wyznaczyć \(\displaystyle{ a_{1000}}\) musisz wyznaczyć wszystkie wyrazy \(\displaystyle{ a_0, a_1,...,a_{999}.}\)

JK

[Jakub Gurak]

A jeśli pytasz o ciąg Fibonacciego, to formalnie nie jest to ciąg, podobnie jak definicja rekurencyjna formalnie nie polega na określeniu ciągu- gdyż dziedziną tej funkcji nie musi być zbiorem liczb naturalnych. Dla przykładu, ciągu Fibonacciego, formalnie jest to funkcja, działająca w sposób poniższy:

\(\displaystyle{ 0 \rightarrow 1,}\)
\(\displaystyle{ 1 \rightarrow 1,}\)
\(\displaystyle{ \left( 1,1\right) \rightarrow 1+1=2,}\)
\(\displaystyle{ \left( 1,2\right) \rightarrow 1+2=3,}\)
\(\displaystyle{ \left( 2,3\right) \rightarrow 2+3=5,}\)
\(\displaystyle{ \left( 3,5\right) \rightarrow 3+5=8,}\)
\(\displaystyle{ \vdots}\)

Więc formalnie nie jest to ciąg, gdyż dziedziną tej funkcji nie jest zbiór liczb naturalnych, tylko pary (niektóre) liczb naturalnych. Ale widać, że taki sposób definiowania jest poprawny, co formalnie potwierdza twierdzenie o definiowaniu przez indukcję. Twierdzenie to mówi, że (w tym przypadku ) istnieje dokładnie jeden ciąg \(\displaystyle{ f:\NN \rightarrow \NN}\), taki, że:

\(\displaystyle{ f(0)=1, f(1)=1, f(2)=2, f(3)=3,\ldots }\)

jak trzeba.


Ciekawy jest też szkic dowodu tego twierdzenia definiowania przez indukcję- aby wykazać, że istnieje ciąg nieskończony, który idzie zgodnie z naszym konstruowaniem, rozważamy rodzinę \(\displaystyle{ \mathbb{H}}\) wszystkich ciągów skończonych, które idą zgodnie z naszym konstruowaniem, i na koniec bierzemy \(\displaystyle{ \bigcup\mathbb{H}}\) jako ciąg nieskończony (co pokazujemy).

[Jan Kraszewski]

A jeśli pytasz o ciąg Fibonacciego, to formalnie nie jest to ciąg, podobnie jak definicja rekurencyjna formalnie nie polega na określeniu ciągu- gdyż dziedziną tej funkcji nie musi być zbiorem liczb naturalnych.

Ciąg Fibonacciego jak najbardziej jest ciągiem i jego dziedziną jest zbiór liczb naturalnych.

Dla przykładu, ciągu Fibonacciego, formalnie jest to funkcja, działająca w sposób poniższy:

\(\displaystyle{ 0 \rightarrow 1,}\)
\(\displaystyle{ 1 \rightarrow 1,}\)
\(\displaystyle{ \left( 1,1\right) \rightarrow 1+1=2,}\)
\(\displaystyle{ \left( 1,2\right) \rightarrow 1+2=3,}\)
\(\displaystyle{ \left( 2,3\right) \rightarrow 2+3=5,}\)
\(\displaystyle{ \left( 3,5\right) \rightarrow 3+5=8,}\)
\(\displaystyle{ \vdots}\)

Że co?! Coś Ci się pozajączkowało. Mylisz definicję rekurencyjną z wynikiem jej działania.

Więc formalnie nie jest to ciąg, gdyż dziedziną tej funkcji nie jest zbiór liczb naturalnych, tylko pary (niektóre) liczb naturalnych. Ale widać, że taki sposób definiowania jest poprawny, co formalnie potwierdza twierdzenie o definiowaniu przez indukcję. Twierdzenie to mówi, że (w tym przypadku ) istnieje dokładnie jeden ciąg \(\displaystyle{ f:\NN \rightarrow \NN}\), taki, że:

\(\displaystyle{ f(0)=1, f(1)=1, f(2)=2, f(3)=3,\ldots }\)

jak trzeba.

I to właśnie ten dokładnie jeden ciąg nazywamy ciągiem Fibonacciego.

JK