262080414

MATEMATYKA DYSKRETNA 2010 2. Wykład 2 - 10.III.2010

2.1. Wyznacznik Vandermonde’a. Z następującego twierdzenia dotyczącego wyznaczników, będziemy korzystać w najbliższej przyszłości.

Twierdzenie 1.

	1	1	1
det	Xi	x2	xn	= n fe - *■
	X™ ^1 #2 ^1		.. a;”^-1	1 <i<3<n

2.2. Równania rekurencyjne liniowe. Równaniem rekurencyjnym liniowym jednorodnym stopnia k nazywamy równanie postaci

(1)    a_n = /(o„_i,...,a_n-fc)

gdzie / : R^fc —> R jest pewną funkcją liniową, oraz zadane są wartości pierwszych k wyrazów ciągu (a_n), ao, ai,..., u/c-i• Przy tych zamych założeniach równanie

(2)    a_n = /(a_n_i,..., a_n-k) + g(n)

Nazywamy równaniem liniowym niejednorodnym stopnia k (o funkcji g : N —» R, poza tym, że jest to funkcja określona w zbiorze liczb naturalnych i o wartościach rzeczywistych, niczego szczególnego nie zakładamy). Dla tak ogólnie postawionego problemu nie będziemy w stanie tu przedstawić metody rozwiązania, niemniej ta postać ułatwi pewne zapisy.

Równaniem rekurencyjnym liniowym o stałych współczynnikach jednorodnym nazywamy równanie rekurencyjne postaci

(3)    a_n = aia_n_i + a₂a_n-2 + ••• + cx_ka_n-_k zaś równanie

(4)    a_n = aia_n_i + a₂a_n-₂ + ... + a_ka_n-_k + g(n)

nazywamy równaniem rekurencyjnym liniowym o stałych współczynnikach

niejednorodnym.

Dla równania (3) równanie

(5)    r^k = Q!ir^fc-1 -(- a₂r^k~² + ... + a_k-ir + a_k

nazywamy równaniem charakterystycznym.

Podczas wykładu zauważyliśmy następujące fakty.

•    Jeśli dane są ciągi będące rozwiązaniami równania (1), to także dowolna kombinacja liniowa tych ciągów jest rozwiązaniem (1) (inaczej mówiąc, zbiór rozwiązań równania (1) jest podprzestrzenią przestrzeni wszystkich ciągów rzeczywistych).

•    Warunki początkowe (czyli wartości ciągu dla pierwszych k indeksów) należą do fc-wymiarowej podprzestrzeni przestrzeni wszystkich ciągów rzeczywistych.

•    Dla każdego rozwiązania r równania charakterystycznego (5) ciąg (rⁿ) jest rozwiązaniem równania (3) (pomijamy w tym rozumowaniu, na razie, warunki początkowe).