Wstep do Teorii Mnogości i Logiki

Lista 7
Zadanie 7.1 Udowodnić indukcyjnie następujące twierdzenia:
n2(n+1)2
(a) (" n " N \ {0}) 13 + 23 + . . . + n3 = ;
4
(b) (" n " N \ {0}) 30 | (n5 - n);
(c) (" n " N \ {0}) (" a, b > 0) a = b Ò! (a - b) | (an - bn);

(d) Dla dowolnej liczby pierwszej p zachodzi: (" n " N \ {0}) p | (np - n).
(a) ("n " N \ {0}) 1 + 5 + 9 + . . . + (4n - 3) = n(2n - 1);
(b) (" n " N \ {0}) 6 | (n3 - n);
(c) (" n " N \ {0, 1, 2}) n2 2n.
Zadanie 7.2 Definiujemy indukcyjnie ciąg Fibonacciego: s0 = s1 = 1, sn+2 = sn + sn+1. Udowodnić, że:
îÅ‚
n+1 n+1 Å‚Å‚
" "
1 1 + 5 1 - 5
ðÅ‚ ûÅ‚
sn = " -
2 2
5
n+1
7
Zadanie 7.3 Definiujemy indukcyjnie ciąg: s0 = 1, s1 = 2, sn+2 = sn + sn+1. Udowodnić, że sn < .
4
Zadanie 7.4 Wykazać, że jeśli iloczyn liczb dodatnich a1, a2, . . . , an wynosi 1, to ich suma jest nie mniejsza niż n.
Zadanie 7.5 Wyrazy ciągu an spełniają następujący warunek: an+2 - 2an+1 + an = 1. Przedstawić wzór na n-ty wyraz
ciągu przy użyciu wyrazów a0, a1.
Zadanie 7.6 Wskazać błędy w następujących rozumowaniach:
(A) Każda liczba naturalna postaci 2n + 1 jest podzielna przez 2.
 Dowód : Jeżeli 2n+1 jest parzysta, to 2n+1=2k, dla pewnej liczby naturalnej k. Wtedy 2(n+1)+1 = 2n+1+2 = 2k+2
= 2(k+1), co kończy dowód.
(B) Dla dowolnej liczby naturalnej n > 0 oraz dowolnego ciÄ…gu liczb rzeczywistych
a1, a2, . . . an spełniona jest nierówność :
|a1 + a2 + . . . + an| |a1| + |a2| + . . . + |an| .
 Dowód : Wzór jest oczywisty dla n = 1. Załóżmy, że wzór zachodzi dla dowolnych n liczb a1, a2, . . . , an. W szczególności,
z założenia indukcyjnego zachodzi dla a1 + a2 + . . . + an i an+1. Zatem, korzystając dwukrotnie z założenia indukcyjnego
otrzymujemy:
|(a1 + a2 + . . . + an) + an+1| |a1 + a2 + . . . + an| + |an+1| |a1| + |a2| + . . . |an| + |an+1| .
Zatem wzór jest przawdziwy dla dowolnych n + 1 liczb.
(C) (" n " N) 30n < 2n + 110.
 Dowód : Załózmy, że twierdzenie jest prawdziwe dla n tzn. 30n < 2n +110. Wtedy 30(n+1) = 30n+30 < 2n +110+30 <
2n+1 + 30, przy czym ta ostatnia nierówność jest spełniona, o ile n 5. Dla n = 1, 2, 3 4 sprawdzamy nierówności
bezpośrednio. Niniejszym twierdzenie zostało dowiedzione.
Zadanie 7.7 Niech p(n) oznacza formułę n2 + 5n + 1 jest liczbą parzystą. Udowodnić, że dla każdej liczby naturalnej n
z prawdziwości zdania p(n) wynika prawdziwość p(n + 1). Następnie sprawdzić, dla których liczb naturalnych to zdanie
jest prawdziwe. Morał zapamiętać.