REKURENCJA.doc

(61 KB) Pobierz
Paweł Grądzki Kl

Paweł Grądzki Kl. II Ti

REKURENCJA

Definicje rekurencyjne

Definicja rekurencyjna (indukcyjna):

·         nieformalnie - taka definicja, która odwołuje się do samej siebie - ale trzeba tu uważać, by odwołanie było do instancji o mniejszej komplikacji,

·         zwykle chodzi o ciąg \left\langle a_0, a_1, a_2, a_3, \ldots \right\rangle, - dla którego przepis na element a_nwykorzystuje jakieś poprzednie elementy: a_{n-1}, a_{n-2}, \ldotsitp.,

·         początkowy element (lub kilka początkowych) muszą być zadane konkretnie - żeby było od czego zacząć,

·         zwykle definicja rekurencyjna odwołuje się do jednego lub kilku poprzednich elementów, ale może też odwoływać się do wszystkich poprzednich.

Przykład

Silnia liczby n(zapisywana jako n!) to iloczyn kolejnych liczb naturalnych od 1do n, czyli

 

n!=n(n-1)\cdot\ldots\cdot2\cdot1.


Przyjmuje się że 0!=1. Oto wartości silni dla kilku początkowych liczb naturalnych

 

\begin{array} {|c|c|c|c|c|c|c|c|c|c|c} \hline n&0&1&2&3&4&5&6&7&8&\cdots\\ \hline n!&1&1&2&6&24&120&720&5040&40320&\cdots\\ \hline \end{array}


Ciąg 0!, 1!, 2!, 3!, 4!,\ldotsaby mógł być precyzyjnie rozumiany np. przez komputer, powinien być zadany rekurencyjnie jako:

 

\aligned s_0 &= 1 \\ s_{n} &= n \cdot s_{n-1} \quad \textnormal{dla} \quad n\geq 1. \endaligned


 

 

 

 

Ponieważ pierwszy wyraz jest zadany, to możemy kolejno obliczać:

 

\aligned s_0 &= 1 \\ s_1 &= 1 \cdot s_{0} = 1 \cdot 1 = 1 \\ s_2 &= 2 \cdot s_{1} = 2 \cdot 1 = 2 \\ s_3 &= 3 \cdot s_{2} = 3 \cdot 2 = 6 \\ s_4 &= 4 \cdot s_{3} = 4 \cdot 6 = 24 \\ \ldots \endaligned

 

Przykład

Jaki ciąg jest zdefiniowany poprzez małą modyfikację w definicji silni?

 

\aligned s_0 &= 0 \\ s_{n} &= n \cdot s_{n-1}\quad \textnormal{dla}\quad n\geq 1 \endaligned


A co definiują następujące określenia:

 

\aligned s_0 &=\frac{1}{2} \\ s_{n} &= n \cdot s_{n-1} \quad \textnormal{dla}\quad n\geq 1 \endaligned


oraz

 

\aligned s_0 &= 1 \\ s_{n} &= n \cdot s_{n-2} \quad \textnormal{dla}\quad n\geq 2. \endaligned

 

W ostatnim przypadku widać, że ponieważ odwołanie jest dwa wyrazy wstecz, to już wyliczenie pierwszego wyrazu s_1staje się niemożliwe.

 

 

Ciąg arytmetyczny

Przykład

W ciągu zadanym poprzez równania:

 

\aligned s_0 &= 0 \\ s_{n} &= s_{n-1}+2 \quad \textnormal{dla}\quad n\geq 1 \endaligned


łatwo rozpoznać kolejne liczby parzyste:

 

s_n = 2n.

 

Ogólnie ciąg zadany poprzez ustalenie a_0oraz

 

a_n = a_{n-1} + r


to tzw. ciąg arytmetyczny.
Jego n-ty wyraz dany jest wzorem:

 

a_n = a_0 + n\cdot r.


Aby to uzasadnić, pokazujemy indukcyjnie, że:

 

a_0 + 0\cdot r = a_0 \quad\textrm{jest rzeczywiście zerowym wyrazem ciągu}

 

 

 

...

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin