|
1. Dokazati da je
za svaki prirodan broj n:
1 - 1/2 + 1/3 - ... + 1/(2n-1) - 1/(2n) = 1/(n+1)
+ 1/(n+2) + ... + 1/(2n)
Rešenje
za n=1: 1 - 1/2 = 1/2
IH:
Pretpostavimo da je tvrđenje tačno za
neki prirodan broj n i dokažimo da važi za n+1:
1 - 1/2 + 1/3 - ... + 1/(2n-1) - 1/(2n) + 1/
(2n+1) - 1/(2n+2)
= 1/(n+1)
+ 1/(n+2) + ... + 1/(2n) + 1/
(2n+1) - 1/(2n+2)
= 1/(n+2) + ... + 1/(2n) + 1/ (2n+1) + 1/(2n+2)
2. Dokazati da članovi
Fibonačijevog niza (F1=F2=1,
Fn=Fn-1 +Fn-2 za n >= 3)
zadovoljavaju nejednakost
Fn <= φn-1
gde φ je broj (1+√5)/2
Rešenje
Za n=1:
F1=1=φ0
=φn-1,
pa je baza indukcije dokazana (tj. da tvrdnja važi za n=1)
Za n=2:
F2=1<1.6<φ1
=φ2-1
Sada pretpostavimo (tj.postavimo IH) da je
tvrđenje tačno za 1,2,...n i važi n>1.
To znači da tvrđenje važi i za n-1
tj.
(i)Fn-1<=φ
n-2
i važi za n, tj.
(ii) Fn<=φn-1.
Kako za članove Fibonačijevog niza važi
(iii) Fn+1=Fn-1 +Fn
<=φ n-2
+φ n-1=φ
n-2(1+φ ) .
Sada interveniše
sledece svojstvo broja φ.
Naime, neposredno se
proveri da je φ2=φ
+1
Stavljajući to u (iii) daje Fn+1<=φn
, pa je dokazano da je tvrdjenje tacno za n+1
Verovatno se secate da ako zelimo da dokazemo da
tvrdjenje P(n) je tačno za sve prirodne brojeve n onda
postoje dva ključna poddokaza:
1)dokazati da je tacno P(1)
2)Ako je tacno P(1),P(2),...P(n) dokazati da je
tacno P(n+1)
U našem zadatku obavljen je 1).
Ali pre koraka 2, pokazali smo direktnom proverom
da je tvrdjenje tacno za n=2. Da li je to suvišno?
Ne,
jer u koraku 2) od značaja nam je pretpostavka da tvrdjenje
važi za n-1.
I ako bi izostavili proveru za n=2 i pokušali
da dokažemo da za n=1, važi tvrđenje za n+1=2 morali bi da
se oslanjamo na to da tvrđenje važi za
Fn-1=F1-1=F0, a
ne možemo referisati na član F0, jer taj član
ne figuriše u formulaciji zadatka.
Za razmišljanje: Koji je odnos Fn
i φn-2.
3. (jun 2001/02)
Dati su za n >=2
prir.brojevi d1, d2,...,dn takvi
da im je zbir 2n-2. Da li postoji stablo sa n čvorova čiji
su stepeni brojevi d1,d2,...,dn
?
Rešenje
Odgovor je postoji. Dokažimo to.
Stepen čvora je broj grana koje su mu
susedne. U mnogim zadacima se koristi cinjenica da sabiranje
stepena cvorova d1+...+dn je isto sto i
brojanje grana, pri cemu se svaka grana broji tacno dva puta.
Dakle, u ovom zadatku se radi nad stablom (ne
mora da je binarno) i dokaz se izvodi indukcijom po n (broju
čvorova)
Baza:
Ako n=2 je d1+d2=2
=>d1=d2=1 i postoji ovakvo stablo, jer dva cvora
povezana granom jesu upravo stablo koje ima 2 cvora i to oba
stepena 1
IH:
Pretpostavimo da je tvrđenje tačno za
n-1 brojeva i neka je dato n>=3 prirodnih brojeva d1,d2,...,dn
ciji je zbir d1+...+dn=2n-2.
Tada postoje bar jedno i
(1<=i<=n), bar jedno j(1<=j<=n)
tako da di=1, dj>1. Zašto?
SP: Za svako i<=n da su
di≠1. Tada ne može biti d1+...+dn=2n-2
(IH)
Slično za dj se
pretpostavi suprotno: za svako j <=n je dj
<=1 .
Tada je d1+..+dn
<=n, a opet za n>=3 je n<2n-2.
Izbacimo iz skupa di i
umanjimo dj za jedan i dobice se skup za koga po IH
postoji stablo sa tim stepenima.
Zatim na to stablo dodamo novi
cvor, zapravo list stepena di=1 prikacenog za cvor
stepena dj-1>=1 i dobija se stablo iz f-lacije
zadtaka, tj. stablo sa n čvorova stepena d1,d2,....dn
.
Rešenje problema u opštem slučaju nije
jedinstveno.
4.(Oprez sa indukcijom)
Šta je pogrešno u sledećem "dokazu"
kojim se želi dokazati tvrđenje:
Za svako pozitivno
realno a i za svaki prirodan broj n je
an-1 =1.
"Dokaz" : n=1 =>an-1
=a1-1=1
IH:Pretpostavimo da je to tačno za 1,2,...,n
Tada: a(n+1)-1=an= (an-1 *
an-1) / an-2 = (1 * 1)
/ 1 = =1, pa je takodje tvrđenje ispunjeno za n+1.
Rešenje
Problem je što nismo smeli pretpostaviti
da je tvrđenje tačno za n=2.
Naime, u drugom delu
dokaza, ako je 2=n+1 (tj. n=1) koristi se da imenilac an-2=1,
a ako je 2=n+1, onda n-2 =-1 i nije korektno pretpostaviti da
a-1=1.
|
