Zadania z przedmiotu
Matematyka Dyskretna, II semestr
seria 1
1. Udowodnić,że
n(n+1)(2n+1)
(1) 12 + 22 + · · · + n2 = ;
6
n2(n+1)2
(2) 13 + 23 + · · · + n3 = (1 + 2 + · · · + n)2 = ;
4
n(n+1)(n+2)
(3) 1 · 2 + 2 · 3 + · · · + n · (n + 1) = ;
3
n
1 n
(4) = ;
i=1
i(i+1) n+1
n
(5) i · 2i = 2 + (n - 1) · 2n+1;
i=1
i-1
n 2n-1
(6) (1 + x2 ) = 1 + xi;
i=1 i=1
2. Udowodnić, że dla każdej liczby naturalnej n
(1) 2n > n;
(2) 30 | n5 - n;
(3) 43 | 6n+2 + 72n+1;
(4) 64 | 32n+1 + 40n - 67;
n5 n3 7n
(5) + + jest liczba naturalna.
5 3 15
3. Dowieść, że jeśli wyrazy ciagu {an} spelniaja nastepujace warunki: a0 = 2, a1 = 3, an+1 =
3an - 2an-1, to an = 2n + 1.
4. Dane sa ciagi {an} i {bn} takie, że a1 = 1, b1 = 1 oraz an+1 = an + 2bn, bn+1 = an + bn.
Dowieść, że
" " "
1 1" "
an = [(1 + 2)n + (1 - 2)n], bn = 2[(1 + 2)n - (1 - 2)n].
2 4
5. Definiujemy rekurencyjnie ciag {an} warunkami: a0 = a1 = a2 = 1 oraz an = an-1 + an-3 dla
n 3.
(1) Oblicz an dla n = 3, 4, 5, 6, 7; Udowodnij, że an 2an-2 dla n 3;
"
(2) Udowodnij, że zachodzi nierówność an ( 2)n-2 dla n 2;
n-1
3
(3) Udowodnij, że an dla n 1.
2