Diskrétní matematika - cvičení 11. týden
Lukáš Vokřínek
Masarykova univerzita Fakulta informatiky
jaro 2020
Poznámka
Pripomeňme si z minule: posloupnost je vpodstatě to samé co mocninná řada
oo
3nxn = a0 + aix + a2x2 H----
která má někdy součet, jímž je funkce f (x), které říkáme generující funkce posloupnosti. V dalším se nám bude hodit dodefinovat an = 0 pro n < 0, takže lze v mocninné řadě sčítat přes všechna celá čísla a nemusíme tak meze příliš řešit.
Poznámka
Funkce x • f(x) je zřejmě
x •      3nxn =      anxn+1 = aox + aix2 + a2X3 + • • •
= ^ an_ixn = 0 + a0x + aix2 + a2x3 H----
a je tedy generující funkcí posloupnosti (0, ao, ai,...), jejíž r?-tý člen je an_i (tady se hodí, že pro r? = 0 jsme dodefinovali a_i = 0). Můžeme ji značit (an_i).
Funkce x • f(x) je zřejmě
x •      3nxn =      anxn+1 = aox + aix2 + a2X3 + • • •
= ^ an_ixn = O + a0x + aix2 + a2x3 H----
a je tedy generující funkcí posloupnosti (0, ao, ai,...), jejíž n-tý člen je an_i (tady se hodí, že pro r? = 0 jsme dodefinovali a_i = 0). Můžeme ji značit (an_i).
Podobně x2 • ^(x) je generující funkcí posloupnosti (an_2).
Príklad
Najděte vytvořující funkci a explicitní vyjádření pro r?-tý člen posloupnosti {an} defiované rekurentním vztahem
a0 = l,3i = 2
an = 4an_i — 3an_2 + 1 pro n > 2
Najděte vytvořující funkci a explicitní vyjádření pro r?-tý člen posloupnosti {an} defiované rekurentním vztahem
a0 = l,ai = 2
an = 4an_i — 3an_2 + 1 pro n > 2
■v
Řešení
Doplňme a_i = a_2 = 0 a rozepišme podrobně druhou rovnici pro případ n = 1, r? = 0:
r? = 1: ai = 4ao — 3a_i + 1 — 3 n = 0: a0 = 4a_i - 3a_2 + 1 + 0
Dohromady tak můžeme psát rekurenci jedinou formulkou: an = 4a„_i - 3an_2 + 1 - 3 • [n = 1] + 0 • [n = 0].
Řešení
an = 4a„_i - 3an_2 + 1 - 3 • [n = 1] + O • [n = 0].
Tu nyní vynásobíme x" a sečteme přes všechna n = 0,1,..., čímž dostaneme:
a„x" = 5](4a„_i - 3an_2 + 1 - 3 • [n = 1] + 0 • [n = 0]) =     4a„-ix" - Y, 3an-2x" +     x" - 3x + 0.
X
n
4x-E an-ix"-1     3x2-X: an_2x"-2
Označíme f(x) vytvořující funkci posloupnosti tj
oo
oo
oo
f (X) = Y, *nX" = Yl Zn-ix"'1 = £ an_2x"
-2
n=0
n=0
n=0
(tady se hodí, že a_i = a_2 = 0, jinak by v těch posledních dvou výrazech byly členy navíc). Tím se rovnice přepíše na
Řešení
f (x) = 4x • f (x) - 3x2 • f (x) + -
— 3x.
— x
Převedením výrazů obsahujících f(x) na levou stranu a vytknutím dostaneme
1
(l-4x + 3x^)-f(x) = -
-3x
— x
neboli
(l-3x)(l-x)-r(x) =
1 - 3x + 3x' 1 -x
Podělením koeficientem u f(x) pak
f(x) =
1 - 3x + 3x2 (l-x)2(l-3x)-
>0 0,0
Řešení
Rozklad na parciální zlomky dá
f (x) = 3/4 • --1/2 •      1 xo + 3/4 1
— x
(1 - x)=
1 - 3x
a rozvinutím do mocninné řady pomocí zobecněné binomické věty
< m=3/4-e (ôV-^-e (" X 1)*"+3/4-e (ô) íy:
Celkový koeficient u xn, tj. r?-tý člen posloupnosti a„, tedy je
*» = 3/4-©-l/>-(T)+3/4-GV = 3/4-l/2-(n+l) + 3/4-3".
>0 Q,o
Pomocí vytvořující funkce vyřešte následující rekurenci:
a0 = 1, ai = 2
an = 5an_i — 4an_2 pro r? > 2
Príklad
Pomocí vytvořující funkce vyřešte následující rekurenci
a0 = 1, ai = 2
an = 5an_i — 4an_2 pro r? > 2
Řešení
Doplňme a_i = a_2 = 0 a rozepišme podrobně druhou rovnici pro případ n = 1, r? = 0:
r? = 1: 3\ — 5ao — 4a_i — 3 n = 0: ao = 5a_i — 4a_2 + 1
Dohromady tak můžeme psát rekurenci jedinou formulkou: an = 5a„_i - 4an_2 - 3 • [n = 1] + 1 • [n = 0].
>0 0,0
Řešení
an = 5an_i - 4an_2 - 3 • [n = 1] + 1 • [n = 0].
Tu nyní vynásobíme xn a sečteme přes všechna n = 0,1 dostaneme:
■v ✓ -v
, cimz
^2 anXn = J^53""1 ~ 4a""2 - 3 • [n =
1] + 1 • [n = 0]) -x" 3x + 1.
Označíme r(x) vytvořující funkci posloupnosti {an}, tím se rovnice přepíše na
f(x) = 5x • f(x) - 4x2 • f(x) - 3x + 1.
>0 0,0
Řešení
f (x) = 5x • f (x) - 4x2 • f (x) - 3x + 1.
Převedením výrazů obsahujících f(x) na levou stranu a vytknutím dostaneme
(1 - 5x + 4x2) • f(x) = -3x + 1
neboli
(1 - 4x)(l - x) • f(x) = -3x + 1
Podělením koeficientem u f(x) pak
f(x) =
-3x + 1 (l-x)(l-4x)'
Řešení
Rozklad na parciální zlomky dá
f(x) = 2/3 • ^— + 1/3 1
1 -x
1 - 4x
a rozvinutím do mocninné řady pomocí zobecněné binomické věty
f(x) = 2/3.X;(j)xn + l/3-$:(j)(4x)n. Celkový koeficient u xn, tj. n-tý člen posloupnosti an, tedy je
n
an = 2/3- [ Q 1+1/3 = 2/3 + 1/3-4".
0
4"
□       rS? ► <     ► < =
Příklad
Pomocí vytvořující funkce vyřešte následující rekurenci
a0 = l,ai = 1
an = a„_i + 2a„_2 + (-1)" pro n > 2
Príklad
Pomocí vytvořující funkce vyřešte následující rekurenci
a0 = l,ai = 1
an = a„_i + 2a„_2 + (-1)" pro n > 2
Řešení
Doplňme a_i = a_2 = 0 a rozepišme podrobně druhou rovnici pro případ n = 1, n = 0:
n = 1: ai = a0 + 2a_i + (-1)1 + 1 n = 0: a0 = a_i + 2a_2 + (-1)° + 0
Dohromady tak můžeme psát rekurenci jedinou formulkou:
a„ = a„_i + 2a„_2 + (-1)" + 1 • [n = 1] + 0 • [n = 0].
Řešení
3n = a„-i + 2a„_2 + (-I)" + 1 • [n = 1] + O • [n = 0].
Tu nyní vynásobíme xn a sečteme přes všechna n = 0,1,..čímž dostaneme:
J2 anxn = + 2an_2 + (-1)" + 1 • [n = 1] + 0 • [n = 0]) • xn
Van_ix" + V 2a„_2xn +-^—
+ x.
X
-2
Označíme r(x) vytvořující funkci posloupnosti {an}, tím se rovnice přepíše na
f (x) = x • f (x) + 2x2 • f (x) + + x.
Řešení
f (x) = x ■ f (x) + 2x2 ■ f (x) + + x.
+ X
Převedením výrazů obsahujících f(x) na levou stranu a vytknutím dostaneme
1
(l-x-2x<)-f(x) = — +x
neboli
x2 +x+l
(l-2x)(l + x).r(x) = —+x Podělením koeficientem u f (x) pak
f(x) =
x2 + X + 1
(l + x)2(l-2x)'
Rozklad na parciální zlomky dá
f (x) = -1/9 • —í— + 1/3 • .   1     + 7/9 • —í— v 7        1     1 + x      7     (1 +x)2      7     1 - 2x
a rozvinutím do mocninné řady pomocí zobecněné binomické věty
f(x) = -
+7/9-E(o)(2x)" Celkový koeficient u xn, tj. n-tý člen posloupnosti an, tedy je
a"= ~1/9' (o)+1/3' C i 0+ 7/9' (o) r
= -1/9 • (-1)" + 1/3 • (n + l)(-l)n + 7/9 • 2".
i ir
Příklad
Vyřešte rekurenci
a0 =
tedy najděte předpis pro
: 0
= a„_i + n pro n > 1 an = l2 + 22 + --- + n2.
Príklad
Vyřešte reku re n c i
30 = 0
an = an-i + n2 pro n > 1
tedy najděte předpis pro an = l2 + 2Z + • • • + n
Řešení
Doplňme a_i = 0 a rozepišme podrobně druhou rovnici pro případ n = 0:
n = 0: 30 = 3-i + O2 + 0 Dohromady tak můžeme psát rekurenci jedinou formulkou:
3„ = 3„_l + A72 + 0-[A7 = 0].
Řešení
an = an_i + n2 + 0-[n = 0].
Tu nyní vynásobíme xn a sečteme přes všechna n = 0,1 dostaneme:
■v ✓ -v
, cimz
5>nx" = 5>n_! + n2 + 0 • [n = 0])
X
e a"-*x"+en
2-x"
Jako minule vyjádříme
n2 = 2-
n+ 2'
-3-
e"
2-x"
V-V-'
n2+3n+2 1
= 2 •
(l-x>
-3-
(l-x)=
+ 1
1 -x
100,0
Řešení
Označíme ř~(x) vytvořující funkci posloupnosti {sn}, tím se rovnice přepise na
f(x) = x ■ f(x) + 2 • ————— - 3 • ^ + 1
(1-x):
1 -x
Převedením výrazů obsahujících ř~(x) na levou stranu a vytknutím dostaneme
111
(1 - x) • f(x) = 2 ■ --- - 3 • —-— + 1
(1-x)
Podělením koeficientem u f(x) pak
(i-xy
1 -x
111
f(x) = 2 • ,„ - 3 • ,„ + 1
(1 - x)'
(1-x)
(1 - x)=
Řešení
f (x) = 2
-3-
+ 1
(1-x)4    ~   (1-x)3 (1-x)2 Rozvinutím do mocninné řady pomocí zobecněné binomické věty
w = 2-E(";>"-3E(n2>" + z:("t1|x"-
Celkový koeficient u x", tj. n-tý člen posloupnosti an, tedy je
,n + 3\ fn + 2\     fn + 1
a„ = 2.|   3     -3-     2     + 1
Řešení
f (x) = 2
-3-
+ 1
(1-x)4    ~   (1-x)3 (1-x)2 Rozvinutím do mocninné řady pomocí zobecněné binomické věty
^) = 2-E("t3V-3EÍ":2V+E^"+1^
Celkový koeficient u x", tj. n-tý člen posloupnosti an, tedy je
,n + 3\ fn + 2\     fn + 1
a„ = 2.|   3     -3-     2     + 1
Úzce to samozřejmě souvisí s:
n> = 2.l" + í)-3.(n+1) + {n + 0
>0 c\o