Zoran Skoda mat1-201120

Primjer dokazivanja pomoću matematičke indukcije.

$$(1 - 1/3)(1 - 1/4)...(1 - 1/n) = 2/n, n \geq 3$$

1) baza indukcije $n=3$

je li (1 - 1/3) = 2/3 ???

Zaista, 3/3 - 1/3 = 2/3 je točno.

2) korak indukcije

Pretpostavimo da tvrdnja vrijedi za neki proizvoljni prirodni broj $n$, vrijedi li onda i za $n+1$, odnosno vrijedi li pod tom pretpostavkom da i

(1 - 1/3)(1 - 1/4)…(1 - 1/n)(1 - 1/(n+1)) = 2/(n+1) ?

Prema pretpostavci koraka indukcije, svi množitelji s lijeve strane osim posljednjeg u umnošku daju $2/n$ pa ćemo je zamijeniti s $2/n$. Lijeva strana je jednaka

$$(2/n)\left(1 - \frac{1}{n+1}\right) = \frac{2}{n}\left(\frac{n+1}{n+1} - \frac{1}{n+1}\right)$$

$$= \frac{2}{n}\frac{(n+1)-1}{n+1} = \frac{2 n}{n(n+1)} = \frac{2}{n+1}$$

Voilà! Dobili smo desnu stranu. Dakle, korak indukcije je dokazan.

Rekurzija

Ako je u gornjem primjeru $A_n$ lijeva strana relacije u koraku indukcije, onda vrijedi

$$A_{n+1} = A_n\cdot\left(1 - \frac{1}{n+1}\right)$$

$A_3 = 1 - 1/3$

$$A_7 = A_6 (1-1/7) = A_5 (1-1/6)(1-1/7) = A_4 (1-1/5)(1-1/6)(1-1/7) = A_3 (1-1/4)(1-1/5)(1-1/6)(1-1/7) = (1-1/3)(1-1/4)(1-1/5)(1-1/6)(1-1/7)$$

Teorem o primitivnoj rekurziji implicira u ovom slučaju da postoji jedinstvena funkcija $A: n\mapsto A_n$ i za koju vrijedi

$$A_{n+1} = A_n \cdot \left(1 - \frac{1}{n+1}\right)\,\,\,\,\,(rekurzivna,\,\,\,relacija)$$

$A_3 = 1 - 1/3$ (početna vrijednost ili baza rekurzije)

Teorem o primitivnoj rekurziji kaže da ako zadamo rekurzivnu relaciju gdje je $A_{n+1}$ pomoću $A_n$ i zadan je $A_1$ tada postoji, pri tome jedinstvena, funkcija $n\mapsto A_n$ koja zadovoljava rekurziju i početne vrijednosti (vrijednost od $A_1$). U praksi rekurzivna relacija izražava $A_{n+1}$ pomoću više nižih (ovdje 2) pa tada treba za bazu staviti nekoliko prvih vrijednosti (onoliko koliko je potrebno da svaka slijedeća relacija bude dobro definirana), recimo $A_1$ i $A_2$ da bi imali zaključak teorema.

Primjer rekurzije su Fibonaccijevi brojevi,

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…

Baza rekurzije, odnosno početne vrijednosti su $F_1 = 1, F_2 = 1$, a rekurzivna relacija je $F_{n+1} = F_n + F_{n-1}$. Svaki Fibonaccijev broj, počevši od $F_3$ je zbroj prethodna dva Fibonaccijeva broja.

Fibonaccijevi brojevi se mogu izraziti preko zlatnog reza koji je jedinstveni racionalni broj veći od $1$ koji je za $1$ veći od svoje recipročne vrijednosti. To znači da je rješenje jednadžbe

$$x - 1/x = 1$$

koja je ekvivalentna jednadžbi

$$x^2 - x - 1 = 0$$

Zbrajanje prirodnih brojeva

• pomoću rekurzije i brojenja

Mi znamo $n+1$, jer znamo brojiti (to je sljedbenik od $n$) pa kako definirati rekurzivno $n+m$ za ma koji prirodni broj $m$ ? Dakle, želimo svesti pribrajanje broja $m$, na pribrajanje manjih brojeva, uključujući pribrajanje broja $1$, odnosno uzimanje sljedbenika.

početna vrijednost (baza) rekurzije: n+1 = sljedbenik od n

Dalje koristimo ideju: recimo n+7 = (n+6)+1

Dakle rekurzijska relacija (korak rekurzije) je n+(m+1) = (n+m)+1. Lijeva strana je ono što želimo odrediti/definirati rekurzijom za $m+1$, a desna strana koristi sljedbenika i pribrajanje manjeg broja $m$.

Na primjer, 3+7 = (3+6)+1 = ((3+5)+1)+1 = (((3+4)+1)+1)+1) = ((((3+3)+1)+1)+1)+1) = (((((3+2)+1)+1)+1)+1)+1)= ((((((3+1)+1)+1)+1)+1)+1)+1)

Može se pokazati da zbrajanje ima svojstva komutativnosti $m+n= n+m$ i asocijativnosti $(n+m)+p = n+(m+p)$.

Zbrajanje se svodi na brojenje!

Množenje

Množenje ćemo označavati s $\cdot$ ili, nekad u shematskom/tekstualnom opisu, s $\times$. Kod kardinalnih brojeva množenje se opisuje brojenjem Kartezijevog umnoška. Ako krenemo aksiomatski (recimo Peano-Dedekindovim aksiomima) ili ako želimo izbjeći previše oslanjanja na skupovne operacije, možemo sve operacije definirati rekurzijom. Rezultat množenja je umnožak ili produkt.

Množenje se rekurzivno svodi na zbrajanje

$3\times 4 = 3+3+3=3$

$3\times 9 = 3+3+3+3+3+3+3+3+3$

$$3\times 9 = 3\times 8 + 3= (3 \times 7 + 3) + 3$$

Množenje ima svojstvo komutativnosti $m+n=n+m$ i asocijativnosti $(m\cdot n)\cdot k = m\cdot(n\cdot k)$.

Potenciranje

rekurzivno se svodi na množenje:

$3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3 = 3^7$

$3^7 = 3^6\times 3$

baza rekurzije $3^1 = 3$

korak rekurzije $3^{n+1} = 3^n\times 3$

Oduzimanje (razlika dva prirodna broja)

Što znači razlika dva prirodna broja ? Koji broj je razlika i kad razlika postoji ?

3 - 2 = 1 zato jer 1 + 2 = 3

6 - 3 = 3 zato jer 3 + 3 = 6

a - b = c akko b + c = a

a je po definiciji veći od b ako postoji broj c tako da je b+c =a tj. ako postoji razlika a-b

Razlika dva prirodna broja je broj koji treba pribrojiti drugom broju da dobijemo prvi, ako taj broj postoji. Ako razlika postoji, kažemo da je prvi broj veći od drugog.

Na taj način dobijemo relaciju uređaja na skupu prirodnih brojeva. Brojevna crta poredamo brojeve, slijeva nadesno, do svakog broja njegov sljedbenik. Broj je veći od $m$ ako je (bilo kolko mjesta) nalijevo od $m$, jer treba pribrojiti broj, a tada se mičemo nalijevo. Zaista, pribrajanje se svodi na uzastopno brojenje, znači na operaciju sljedbenika koja znači pomak ulijevo.

$$1 \lt 2\lt 3 \lt 4 \lt 5$$

Množenje NIJE komutativno. Npr. $2^7 = 128$, a $7^2=49$. Nije ni asocijativno, $(a^b)^c\neq a^{b^c}$ i ovaj drugi izraz je veći kod prirodnih brojeva $a,b,c\gt 1$ osim ako su sva tri jednaka $2$. Vrijedi $(a^b)^c = a^{b c}$, a $b c$ je tipično manji od $b^c$, osim za $b=1$ ili $c=1$ (ili kad su oba $2$ kad su jednaki).

Dijeljenje

Rezultat operacije dijeljenja na parovima prirodnih brojeva $(m,n)$ označavamo s $m:n$ ili $m/n$ ili $\frac{m}{n}$. Recimo, promatrajmo $8:4$. Tu vidimo dva argumenta, naime

djeljenik (kojeg dijelimo, 8)

djelitelj (koji dijeli, 4)

a rezultat dijeljenja zovemo količnik (kvocijent).

Kažemo da je 8 : 4 = 2 jer je $2 \times 4 = 8$.

Kvocijent dva prirodna broja je prirodni broj s kojim trebamo pomnožiti drugi da dobijemo prvi (djelitelja da dobijemo djeljenika). Kako u našem primjeru takav broj postoji, naime 2, tako kažemo da je 8 djeljivo s 4, ili da 4 dijeli 8.

S druge strane, ne postoji prirodni broj $n$ takav da je $8 = 3 n$. Broj 8 nije djeljiv s 3, međutim, u skupu prirodnih brojeva 8 : 3 možemo djelomično podijeliti.

Kažemo da je 8 : 3 = 2 s ostatkom 2. Umjesto da bi 8 podijelili s 3, mi smo zapravo 8 razdijelili na 6 i 2, i podijelili 6 s 3. Broj 6 je djeljiv s 3 i on je dio od 8, pa kažemo da smo dijelili djelomično. U ovom slučaju, 6 je najveći dio (broj manji od 8) koji možemo podijeliti s 3

$$6:3 = 2,\,\,\,\,\,\,\,\, 8 = 3 \times 2 + 2$$

Takvo djelomično dijeljenje, u kojem smo podijelili najveći djeljivi dio od 8, i ostatak je manji od broj s kojim dijelimo (djelitelj), zovemo dijeljenje prirodnih brojeva s ostatkom. Svaka dva prirodna broja možemo na jedinstveni način podijeliti s ostatkom ( teorem o dijeljenju s ostatkom, vidi prirodni broj).

Možemo djelomično dijeliti, a da ne dijelimo najveći mogući dio, no tada će ostatak biti veći od djeljenika. Makar i dalje govorimo o ostatku, obično ne govorimo o dijeljenju brojeva s ostatkom (to bi bio gornji slučaj, kad je ostatak najmanji mogući, naime manji od broja s kojim dijelimo), nego radije naglašavamo “djelomično” dijeljenje. Recimo, gledajmo ovo djelomično dijeljenje, kažemo da je $8 : 3 = 1$ i $5$ ostatak, jer $8 = 3\times 1 + 5$. Kako $3$ nije najveći dio od $8$ za koji to možemo napraviti, ovo nije potpuno dijeljenje s ostatkom, nego samo djelomično dijeljenje. Kad je broj dijeljen, tj. ostatka nema, kažemo da je ostatak $0$, što ima smisla kad skup prirodnih brojeva proširimo do $\mathbf{N}_0 :=\mathbf{N}\cup\{0\}$ sa standardnim proširenjem algebarskih operacija s $\mathbf{N}$ na $\mathbf{N}_0$ gdje se operacije ne mijenjaju ako su oba argumenta iz $\mathbf{N}$, a kad je jedan ili oba argumenta $0$, tada

1. Za ma koji $m\in\mathbf{N}_0$ definiramo $m+0 = m = 0+m$, $m\cdot 0 = 0 = 0 \cdot m$, $m-0 = m$

2. Za ma koji $n\in\mathb{N}$ definiramo $n^0 = 1$, $0^n=0$ i $0/n=0$.

3. Izrazi $n/0$, $0/0$ i $0^0$ nisu definirani.

Dijeljenje s ostatkom je djelomično dijeljenje (znači podijelimo samo neki dio koji se da dijeliti) u kojem je ostatak manji od onoga s čime dijelimo (djelitelj) i ono se uvijek može napraviti na jedinstveni način (egzistencija i jedinstvenost ovdje su sadržaj teorema o dijeljenju s ostatkom, vidi prirodni broj)

$$\array{ &2&6&7&3&\colon 14 = 190\\ -&1&4&\\ &1&2&7\\ -&1&2&6\\ &&&1&3 }$$

to znači da je $190\times 14 + 13 = 2673$

$$190\times (10 +4) = 1900 +760 = 2660$$

2660 + 13 = 2673

Mjesni sustavi pisanja brojki

Razlikujemo broj, brojku i znamenku. Broj je matematički pojam, brojka je oznaka za broj, a znamenka je dio brojke koji je nezvisni simbol u jednom od mjesnih sustava.

Broj – apstraktna veličina (npr. kardinalni broj ili iterirani sljedbenik od sljedbenika…od jedinice u Peanovim aksiomima, recimo $s(s(s(s(1)))) = ||||| = 5$) – broj kao matematički entitet

Znamenka – pojam o tome kako gradimo brojke iz nekog skupa znakova koje zovemo znamenke, a one su u mjesnom sustavu, što znači da vrijednost znamenke ovisi o njenom mjestu u nizu. Dakle 21 nije isto što i 12. 2 na prvom mjestu znači 2 desetice, to mjesto ima neku težinu.

Brojka je neko standardno ime/cjelovita oznaka za određeni broj. Kad su se uveli simboli za neke brojeve, tada je nizanje brojeva bilo slično tumačenju količine novca – simboli se zbrajaju kao monete. Nanizanih 8 oznaka za broj 1, recimo 11111111 bi u toj logici značilo 8. To je prirodni sustav, ali nepraktičan. Primijetite također da je 12 isto kao i 21 u tom prirodnom sustavu koji nije mjesni sustav, jednostavno imamo 1+2.

Kod Rimljana je sustav gdje ne možemo mjestima postići bilo koji broj nego samo zbrajamo, ali nekad i oduzimamo, što ovisi o poretku. Tako je 9 = 10-1 označeo s IX, a 11 označeno s XI, gdje X označava 10, a I jedinicu.

Rimljani X 10, V 5, M 1000, I 1, L 50, C 100.

IX 9, XI 11, XVI 16, XVII 17, XVIII 18, ali nije dozvoljeno pisati XVIIII za 19 nego XIX. Samo neka oduzimanja su dozvoljena.

Suvremeni mjesni sustavi: najlakše je objasniti standardni dekadski sustav, za kojeg kažemo da ima bazu 10. Naime,

345 nije 3+4+5 nego $3\times 10^2 + 4\times 10^1 + 5\times 10^0$

znamenke u tom sustavu su od 0 do 9

$(345)_{(10)}$

$$(267)_{(8)} = 2 x 8^2+6 x 8+7= 128 + 48 + 7=(183)_{(10)}$$

Idemo obratno – od dekadske brojke 183 dobiti njen oblik u oktalnom mjesnom sustavi.

$$\array{ 1&8&3&\colon 8 = 22 \\ &2&3&\\ & &7&\\ }$$

$$\array{ 2&2&\colon 8 = 2\\ &6& }$$

$$183 = 22\times 8\times 7 = (2\times 8 + 6)\times 8 +7= 2 \times 8\times 8 + 6 \times 8 + 7 = (267)_{(8)}$$

Nekad se upotrebljava notacija u tom postupku oblika

$$\array{ &(8)&\\ 183 &|& 7\\ 22 &|& 6\\ 2 &|& }$$

Rezultat postupka se čita prema gore, 267.

A,B,C,D,E,F su znamenke za 10, 11, 12, 13, 14, 15 u heksadecimalnom sustavu (mjesnom sustavu s bazom 16). Na primjer, $(2A)_{(16)} = 2\cdot 16 + 10 = (42)_{(10)}$

U binarnom sustavu su znamenke $0$ i $1$. Na primjer, $(1011)_2 = 1 x 2^3 + 1x 2 + 1 = 11$

Djeljivost: broj $m$ je djeljiv s $n$ (sinonim: $n$ dijeli $m$) ako postoji njihov količnik $m:n$ (tj. nema ostatka kod dijeljenja brojem $n$), drugim riječima, postoji $k$ prirodan broj, takav da $m = n\cdot k$.

Ako je broj djeljiv s 2 zovemo ga paran broj. Broj je $n$ neparan ako nije paran, odnosno ako se može napisati kao $2\cdot k + 1$ gdje je $k$ prirodan broj ili $0$.

Prebrojavanje (kombinatorika)

Enumerativan kombinatorika se bavi prebrojavanjima konačnih skupova.

Jedan primjer su takozvana premještanja ili permutacije. Ovo je osnovno pitanje: na koliko način možemo poredati $n$ različitih predmeta u slog (konačni niz). Recimo, za tri predmeta a,b,c, mogući poreci su a b c, a c b, b a c, b c a, c a b, c b a. Dakle ukupno 6. Broj mogućnosti jako brzo raste s porastom broja predmeta. Za 5 predmeta, rezultat je $5\cdot 4\cdot 3\cdot 2\cdot 1 = 120 = 5!$, čitamo pet faktorijela. Funkcija $n\mapsto n!$ je definirana primitivnom rekurzijom s početnim uvjetom $1! = 1$ i rekurzivnom relacijom $(n+1)! = (n+1)\cdot n!$.

Kako to vidimo ? Na prvo mjesto možemo staviti jedan od $n$ predmeta, za što imamo $n$ mogućnosti; jednom dok je predmet na prvo mjesto postavljen on je potrošen u smislu da ga ne možemo istovremeno staviti na druga mjesta. Dakle, za slijedeće mjesto imamo $(n-1)$ mogućnosti, pa onda za slijedeće $(n-2)$ i tako dalje, i za zadnje mjesto ostaje nam jedan jedini predmet.

category: zadarmat1