733857I471775725252470485522 n

3Ł ROZDZIAŁ I. POWÓD ME WPROST I OOWÓO IROUKCYJRY

10.4. Udowodnij, że dla każdego /ioV_H

9|r + 3w- 1,

133 111**² + 12²"*¹,

o 6| n^y - n,

g)    42| n⁷ - n,

h)    31 n^ł - n,

101 9 • 3*"+ 1,    j) 5| w^s - n,

11110"-(-1)*,    k) 7| n¹ - n.

10.5. Udowodnij, że:

a) n prostych na płaszczyźnie, z których żadne dwie nic są równoległe i żadne trzy nie

133 1P^T,+ 12

Ł»- l

przechodzą przez ten sam punkt, dzieli płaszczyznę na

n{n l 1)

+ 1 części,

b) jeżeli płaszczyznę podzielimy na części za pomocą prostych i okręgów, to otrzymaną mapę można pokolorować dwoma kolorami,

C) n-kąt wypukły ma ^ przekątnych,

d) n płaszczyzn przechodzących przez jeden punkt, z których żadne trzy nie mają wspólnej krawędzi, dzieli przestrzeń na n(n-1) + 2 części.

10.6. Jeżeli />„ oznacza n-tą liczbę pierwszą (p, “ 2,p₂ -3,pj - 5, itd.), to dla n > 12 spełniona jest nierówność p„ > 3n.

11. OGÓLNA ZASADA INDUKCJI MATEMATYCZNEJ

Na podstawie zasady indukcji matematycznej potrafimy udowodnić prawdziwość wielu twierdzeń. Z zasady indukcji wynika również poprawność wielu definicji. W sposób indukcyjny definiuje się np. pojęcie potęgi o wykładniku naturalnym: x°=I dla x*0,

¹X dla n £ 1.

W sposób indukcyjny określa się wiele ciągów liczbowych. Ciągi tak określone nazywa się ciągami rekurcncyjnymi. Do znanych ciągów rekurencyjnych zalicza się tzw. ciąg Fibonaccicgo¹⁰ określony w następujący sposób:

Ul » 1,

«2“ 1.

u» ° u„-2 + dla /i £ 3.

Kolejnymi wyrazami tego ciągu są liczby: 1, 1, 2,3,5, 8,....

Charakterystyczną cechą tego określenia jest tworzenie wyrazu następnego nic z jednego wyrazu poprzedzającego, ale z dwóch (kilku) wyrazów poprzedzających. Odmiana indukcji, w której krok indukcyjny wyprowadza się z kilku kroków poprzedzających, nosi nazwę ogólnej zasady indukcji matematycznej.

III. Jeżeli

1)    twierdzenie jest prawdziwe dla pewnej liczby n₀,

2)    z prawdziwości twierdzenia dla n takich, że /r<,^ *j £ k wynika prawd2i

tego twierdzenia dla n = k + !,

to twierdzenie jest prawdziwe dla każdej liczby naturalnej n >. n₀.

PRZYKŁADY

1) Każ.da liczba naturalna n £ 2 jest liczbą pierwszą lub iloczynem liczb pierwszy Dowód. Liczba 2 jest liczbą pierwszą, więc twierdzenie jest prawdziwe dla n = Załóżmy, że liczby naturalne n takie, że 2 ś n ś A: są liczbami pierwszymi lub ii liczb pierwszych. Wykażemy, że twierdzenie jest prawdziwe również dla liczb; Jeżeli k +1 jest liczbą pierwszą, to twierdzenie jest prawdziwe. Jeżeli £ + 1 złożoną, to k + ]=s-t, gdzie 2 ś s, t ś k. Ponieważ na mocy założenia ind' liczby s i t są iloczynami liczb pierwszych, więc również k + 1 jest iloczy pierwszych.

ZADANIA

11.1. Ciąg {b„) określony jest wzorem rckurencyjnym: b\ = 1, b,.. i • - b„ + 2n + 1.

11.2. Ciąg (/;„) określony jest wzorem rckurencyjnym: bo - 2. b, - 3, b.., = bi b_n - bo b..,. Wykaż, że b„ - ? + 1.

11J. Udowodnij, że każdą całkowitą nic mniejszą od 4 liczbę złotych można w; pomocą dwuzłotówek i pięciozłotówek.

11.4. Niech p{ri) będzie liczbą liczb pierwszych nie większych od liczby nati Wykaż, że jeśli n Jł 8. to p{n) Ś-.

^    -.-A    /

12. ŚREDNIA ARYTMETYCZNA I ŚREDNIA GEOMETRYC

wiednio średnią arytmetyczną i średnią geometryczną tych liczb .

Twierdzenie. Dla dowolnych nicujcmnych liczb a i b prawdziwa jest nierówność

2

zwana nierównością o średnich. Równość jest możliwa jedynie, gdy a - b.