Dzielenie tortu:
1
4
4
2
1
2
3
pi i
p0 = 1
pn = pn 1 + n
pi i
pi - liczba królików w i
p1 = 1
p1 = 1
p2 = 1
pn = 2pn 1 + 1
pn = pn 1 + pn 2
pn = f(pn 1, pn 2, ... , pn k, n).
Przedstawimy teraz kilka praktycznych sposobów znajdowania
"zwartych" wzorów na n pn = f(n).
Zgadywanie na podstawie kilku wyrazów pocz tkowych Zgadywanie na podstawie wielokrotnego rozwini cia wcze niej-
Zgadywanie na podstawie kilku wyrazów pocz tkowych Zgadywanie na podstawie wielokrotnego rozwini cia wcze niej-
szych wyrazów.
szych wyrazów.
p1 = 1
pn = 2pn 1 + 1 p1 = 1
pn = 2pn 1 + 1
p1 = 1, p2 = 3, p3 = 7, p4 = 15, p5 = 31
= 2(2pn 2 + 1) + 1 = 4pn 2 + 2 + 1 =
Zgadujemy: pn = 2n 1
= 4(2pn 3 + 1) + 2 + 1 = 8pn 3 + 4 + 2 + 1 =
n 1 jest
= 8(2pn 4 + 1) + 4 +2 + 1 = 16pn 4 + 8 + 4 + 2 + 1
dobrze, wówczas mamy pn = 2pn 1 + 1 = 2(2n 1 1) + 1 = 2n 1. Dla n
...
-
= 2ipn i + =
"
=
p0 = 1
= 2ipn i + 2i 1 = /* dla i = n 1 */
pn = pn 1 + n
=2n 1p1 + 2n 1 1 = 2n 1
p0 = 1, p1 = 2, p2 = 4, p3 = 7, p4 = 11, p5 = 16, p6 = 22
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Zgadujemy pn = n(n + 1) / 2 + 1
pn = pn 1 + pn 2 = 2pn 2 + pn 3 = 3pn 3 + 2pn 4 = 5pn 4 + 3pn 5 = ...
Szczególny przypadek - sumy
Szczególny przypadek - sumy
pn = pn 1 + n = (n 1)n / 2 + 1 + n = n(n + 1) / 2 + 1.
cn pn:
p0 = c0
pn = pn 1 + cn
mamy pn = .
"
=
pn = f(n)?
Metoda zaburzania ą
Metoda zaburzania
= + ą ą - -
ą -
+
pn+1 = = + = pn + cn+1
" " +
= =
+
Np. dla ą = 2 mamy: = + -
n+1 n+1 n "
=
pn+1 = = + c0 =
"c "c "c + c0
i i i+1
i=0 i=1 i=0
dla ą = 3 mamy: = + -
"
=
Z równania + = + pn.
"
+ +
= Skomplikuj i upro
Skomplikuj i upro
=
"ą
kf(k
=
-
.
"
=
+
+ ą + =
"ą + !
=
-
+ ą + = ą + !
= = =
" "" "
= = = d" < d"
- ą +
=
n-1 n
k
- ą
""2 =
j=0 k= j+1
n-1 n j
= ą .
k k
"
ł ł
"ł"2 -"2 ł =
=
j=0 k=0 k=0 łł
ł
Otrzymujemy:
n-1 n-1 n-1
j+1 j+1 j
((2n+1 -1) - (2 -1))= (2n+1 - 2 )= n2n+1 - 2 =
" " "2
+ + ą + = + ą + !
"
j=0 j=0 j=0
=
n2n+1 - 2(2n -1) = (n -1)2n+1 + 2
+ + ą + = ą + ą !
"
=
n+1
1-ą
n+1
pn + (n +1)ą = ąpn +ą !
1-ą
+
(2) zmF(z) = = = f0zm + f1zm+1 + ...
" " -
Funkcje tworz ce
Funkcje tworz ce
m pozycji.
F(z
F(z) = p0 + p1z + p2z2 + ... =
"
F(z) = z3
e"
pi = 0 dla i < 0.
m
W zasadzie F(z m
istnieje niepusta jej dziedzina czyli co najmniej jedna liczba z
fk zk -m = fk +mzk fm, fm+1, ...)
" "
k e"m k e"0
szereg
"
Najpierw odejmujemy pierwsze m wyrazów: F(z) f0 ... fm 1zm 1.
e"
"
e" Przesuwamy wszystkie wyrazy o m pozycji w lewo:
-
wie pk
- - -
-
pn = f(n
(4) F(az) = f0, af1, a2f2, ...)
"
-
(5) zF'(z) = = = =
" " " "
Jeszcze jedna umowa: Niech v v]
= 1, gdy v jest prawdziwe i [v] = 0, gdy v
f1, 2f2, 3f3, ...)
-
(6) = + + = + + =
"
+" +"
e"
f1, f2, f3, ...)
Niech F(z) = oraz G(z) =
" "
(7) F(z)G(z) = " = (f0 + f1z + f2z2 + ...) " (g0 + g1z + ...) =
" "
(1) aF(z) + bG(z) = + = +
" " "
= (f0g0) + (f0g1 + f1g0)z + (f0g2 + f1g1 + f2g0)z2 + ... =
"" -
f0g0, f0g1 + f1g0, f0g2 + f1g1 + f2g0, ...)
(8) Niech (gk) = (1, 1, 1, 1, ...).
Wówczas G(z) = 1 + z + z2 + ... = .
n-ty wyraz
-
F(z) = = .
"" - ""
1, 0, 0, ... [n = 0] 1
-
d"
0, ..., 0, 1, 0, 0, ... [n = m] zm
f0, f0 + f1, f0 + f1 + f2, ...)
1, 1, 1, ... 1 1 / (1 z)
1, 1, 1, 1, ... ( 1)n 1 / (1 + z)
z) i mamy
1, 0, ... , 0, 1, 0, ... [m | n]1/ (1 zm)
1, 2, 3, 4, ... n + 1 1 / (1 z)2
+ + +
ł ł ł ł ł -
ł
1 / (1 z)k
ł ł ł ł ł ł
(9) F(zm) = .
"
ł łł ł łł ł łł
1, k, k2, k3, ... kn 1 / (1 kz)
f0, 0, ..., 0, f1, 0, ..., 0, f2, 0, ...)
ł ł ł ł ł ł ł ł
(1 + z)k
ł ł ł ł ł ł ł ł d" d"
ł łł ł łł ł - łł ł łł
e" ln(1 / (1 z))
ez
Wykorzystanie funkcji tworz cych do znajdowania postaci
Wykorzystanie funkcji tworz cych do znajdowania postaci
zwartej ci gów okre lonych rekurencyjnie fn = fn 1 + (n + 1)[n e" 1] + 3[n = 0] | zn
zwartej ci gów okre lonych rekurencyjnie
fn)ne"0 fn =
fnzn = fn 1zn + (n + 1)[n e" 1]zn + 3[n = 0]zn | Ł
f(n).
fnzn = fn-1zn + +1)zn +
" " "(n "3[n = 0]zn
Krok 1 n n ne"1 n
Przedstawiamy fn n oraz
1
F(z) = fnzn+1 + -1+ 3
"
fi dla pewnych i < n
(1- z)2
n 1
+
równania rekurencyjnego.
1
F(z) = zF(z) + + 2
(1- z)2
f-1 = f-2 = ... = 0.
Krok 3
f0 = 3
F(z).
fn = fn 1 + n + 1
fn = fn 1 + (n + 1)[n e" 1] + 3[n = 0]
= +
Krok 2
- -
zn
strony po wszystkich n
Krok 4
Rozwijamy F(z =
"
= .
"
fn n.
F(z),
= + =
oraz zmiennej z.
- -
+
=
ł ł
"ł ł + "
ł łł
e"
ł +
łł
"łł ł + ł
łł ł śł
ł łł
e"
wielomian z mianownika, a G(z) jest ilorazem reszty z tego dzielenia
+ + przez wielomian z mianownika.
= +
Wówczas zamiast F(z G(z) i w
efekcie otrzymujemy F(z
Fibonacciego.
f1 = f2 = 1
fn = fn 1 + fn 2, dla n e" 2.
= - +
+ +
Krok 1
fn = fn 1 + fn 2 + [n = 1] ai, bi, ki?
Krok 2
wielokrotne liczymy wielokrotnie).
= + + = =
" -
" -
"
+ +
Liczba pierwiastków mianownika jest równa stopniowi wielomianu w
+ + =
" "
+ +
zi
+ +
bi = 1/zi, ki = 1.
Krok 3
zi jest pierwiastkiem p-krotnym (p e"
=
p bi = 1/zi, ki = 2, 3, ... , p.
- -
ai
Krok 4
zk dla k = 0,1, ... w
.
-
F(z W(z) +
G(z), gdzie W(z) jest wynikiem dzielenia wielomianu z licznika przez
= .
- -
=
+ -
ą
Mianownik ma dwa pierwiastki:- .
Mamy:
= + + = + + =
+ + +
+ - - + - -
- +
= + =
+ + - -
- + + - + +
+ -
+ -
Porównajmy liczniki:
Prównujemy liczniki:
+ + + =
- +
- + + - - + + =
+ =
ńł
+ + = ł
ńł
,
ł
ł
- - + = = = =
ł ł - + + =
ół
ł
- =
ół
= - =
Czyli
= + + = - +
+ - - + +
+ -
Mamy =
"
-
e"
F(az) = otrzymujemy:
"
=
"
-
e"
= - + =
+ +
+ -
- -
- +
" "
+ -
e" e"
- -
-( ) ( )
+
+ -
A zatem =
n n
1+ 5 1- 5
( ) -( )
2 2
fn =
5
Wyszukiwarka