MATEMANIJA

Dokazati:
[dispmath]\sum_{k=1}^n(-1)^{k+1}{n\choose k}\frac{1}{k}=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}[/dispmath]
Za [inlmath]n=1[/inlmath] jednakost je tačna.
Za [inlmath]n=m[/inlmath]
[dispmath]m-{m\choose2}\frac{1}{2}+\cdots+(-1)^{m+1}\frac{1}{m}=1+\frac{1}{2}+\cdots+\frac{1}{m}[/dispmath]
Za [inlmath]n=m+1[/inlmath]
[dispmath]\left(\sum_{k=1}^m(-1)^{k+1}{m\choose k}\frac{1}{k}\right)+(-1)^{m+2}\frac{1}{m+1}=1+\frac{1}{2}+\cdots+\frac{1}{m+1}[/dispmath]
Iz zadnje jednakosti, ako je [inlmath]m[/inlmath] neparno onda jednakost nije tačna, dok je za [inlmath]m[/inlmath] parno tačna. Naravno, uvrštavanjem nekih vrednosti za [inlmath]k[/inlmath] i [inlmath]m[/inlmath] jednakost je tačna za sve prirodne brojeve.

Kako dokazati ovu jednakost?

Moja prva ideja:
[dispmath]\sum_{k=1}^n(-1)^{k+1}{n\choose k}\frac{1}{k}=\sum_{k=1}^n\frac{1}{k}[/dispmath]
I sada dokazujemo da su opšti članovi jednaki. Bez suma. Zar nije tako?

display_error je napisao:Za [inlmath]n=m+1[/inlmath]
[dispmath]\left(\sum_{k=1}^m(-1)^{k+1}{m\choose k}\frac{1}{k}\right)+(-1)^{m+2}\frac{1}{m+1}=1+\frac{1}{2}+\cdots+\frac{1}{m+1}[/dispmath]

Jesi li siguran da ti je leva strana date jednakosti dobro zapisana? Da nije mozda [inlmath]{m+1\choose k}[/inlmath], ili pak ja gresim?

desideri je napisao:[dispmath]\sum_{k=1}^n(-1)^{k+1}{n\choose k}\frac{1}{k}=\sum_{k=1}^n\frac{1}{k}[/dispmath]
I sada dokazujemo da su opšti članovi jednaki. Bez suma. Zar nije tako?

Pa, nije. Evo za [inlmath]n=2[/inlmath]:
[dispmath]\left(-1\right)^{1+1}{2\choose1}\frac{1}{1}+\left(-1\right)^{2+1}{2\choose2}\frac{1}{2}=1+\frac{1}{2}[/dispmath]
[dispmath]2+\left(-\frac{1}{2}\right)=1+\frac{1}{2}[/dispmath]
Dakle, već za [inlmath]n=2[/inlmath] se vidi da opšti članovi nisu jednaki. Prvi sabirci na levoj i na desnoj strani su [inlmath]2[/inlmath] i [inlmath]1[/inlmath] respektivno, a drugi sabirci na levoj i na desnoj strani su [inlmath]-\frac{1}{2}[/inlmath] i [inlmath]\frac{1}{2}[/inlmath] respektivno.
To što su suma na levoj strani i suma na desnoj strani međusobno jednake, ne znači nužno i da su svi članovi tih suma međusobno jednaki.

Onomatopeja je napisao:Jesi li siguran da ti je leva strana date jednakosti dobro zapisana? Da nije mozda [inlmath]{m+1\choose k}[/inlmath], ili pak ja gresim?

Ne grešiš, zaista treba da stoji [inlmath]{m+1\choose k}[/inlmath].

desideri je napisao:[dispmath]\sum_{k=1}^n(-1)^{k+1}{n\choose k}\frac{1}{k}=\sum_{k=1}^n\frac{1}{k}[/dispmath]
I sada dokazujemo da su opšti članovi jednaki. Bez suma. Zar nije tako?

E ovde mi je promakla greška

Daniel je napisao:To što su suma na levoj strani i suma na desnoj strani međusobno jednake, ne znači nužno i da su svi članovi tih suma međusobno jednaki.

Daniel je dobro ukazao na ovo:
Ne moraju opšti članovi biti jednaki ako su sume jednake.
Mogu da se članovi potiru tu i tamo, parni ili neparni, pa čak i da nema ni dva ista a da su sume iste.
Ovo je jako bitno, thanks Danielu.

Nego da ja razradim svoju početnu ideju:
[dispmath]\sum_{k=1}^n(-1)^{k+1}{n\choose k}\frac{1}{k}=\sum_{k=1}^n\frac{1}{k}[/dispmath]
Ovo je pretpostavka koju treba dokazati.

Hajde da jednu sumu oduzmemo od druge:
[dispmath]\sum_{k=1}^n(-1)^{k+1}{n\choose k}\frac{1}{k}-\sum_{k=1}^n\frac{1}{k}=\sum_{k=1}^n\frac{1}{k}\left((-1)^{k+1}{n\choose k}-1\right)[/dispmath]
Mislim da je lakše posle ove transformacije matematičkom indukcijom dokazati ono što se traži.
Potrebno je pokazati da je suma na desnoj strani jednaka nuli.

@desideri

Induktivni korak, [inlmath]n=m+1[/inlmath]:
[dispmath]\sum_{k=1}^{m+1}\frac{1}{k}\Bigg((-1)^{k+1}{m+1\choose k}-1\Bigg)=0[/dispmath][dispmath]m+\frac{1}{2}\left(\frac{-m(m+1)}{2}-1\right)+\frac{1}{3}\left(\frac{m(m+1)(m-1)}{3\cdot2}-1\right)+\cdots+\frac{1}{m+1}\left((-1)^{m+2}-1\right)=0[/dispmath]
Posebno smeta sabirak [inlmath]\frac{1}{m+1}\left((-1)^{m+2}-1\right)[/inlmath] jer određuje parnost. Da li je potrebno posmatrati odvojene slučajeve,
ili vršiti trasformacije?

Evo pogledaću.
Mislim da je potrebno razmotriti i parnost-neparnost.
No prvo sumu prikaži kao sumu do [inlmath]m[/inlmath] plus [inlmath]m+1[/inlmath] član. tako se radi "induktivna suma".

Znam kako se moze resiti ovaj zadatak. Naime, davno sam naleteo na dati problem i bilo mi je potrebno sad malo vise vremena da se setim tog resenja. Sutra pisem resenje, ali napominjem da resenje ne sadrzi u sebi indukciju i da ima odredjene zackoljice (nije bas jednostavno, tj. pravolinijsko). Mada, ne kazem, mozda ce neko naci i jednostavniji nacin (ali, prvo da ispisem to resenje (to sutra)).

U redu, evo i odgovora. Naime, glavni trik jeste primetiti da vazi [inlmath]\displaystyle\enclose{box}{\frac{1}{k}=\int\limits_0^1t^{k-1}\,\mathrm dt}[/inlmath]. I onda, magija moze da pocne. Naime, sad vidimo da vazi
[dispmath]\sum_{k=1}^n(-1)^{k+1}{n\choose k}\frac{1}{k}=\sum_{k=1}^n\left((-1)^{k+1}{n\choose k}\int\limits_0^1t^{k-1}\,\mathrm dt\right)=\int\limits_0^1\!\left(\sum_{k=1}^n(-1)^{k+1}{n\choose k}t^{k-1}\right)\,\mathrm dt=(*),[/dispmath]
gde smo smeli da udjemo sumom pod ovaj integral, jer je u pitanju konacna suma. Sada, nekako se namece da ova suma pocinje od binomne formule. I zaista, posle malo vise gledanja, uocava se da vazi
[dispmath]\sum_{k=1}^n(-1)^{k+1}{n\choose k}t^{k-1}=\frac{1-(1-t)^n}{t}.[/dispmath]
Zato dobijamo
[dispmath](*)=\int\limits_0^1\frac{1-(1-t)^n}{t}\,\mathrm dt=\int\limits_0^1\frac{1-x^n}{1-x}\,\mathrm dx[/dispmath]
posle smene [inlmath]1-t=x[/inlmath]. Odavde se nazire kako se dobija konacno resenje. Naime, kako je [inlmath]\displaystyle\frac{1-x^n}{1-x}=1+x+\cdots+x^{n-1}[/inlmath], to smo dobili kada sve povezemo
[dispmath]\sum_{k=1}^n(-1)^{k+1}{n\choose k}\frac{1}{k}=\int\limits_0^1\left(1+x+\cdots+x^{n-1}\right)\,\mathrm dx=\sum_{k=1}^n\frac{1}{k},[/dispmath]
integracijom clan po clan.

I za one sumnjicave, tacka [inlmath]1[/inlmath] nije problematicna u prethodnom postupku (deljenje nulom, tralala), jer je skup [inlmath]\{1\}[/inlmath] zapravo skup (Lebegove) mere nula, te mozemo smatrati da [inlmath]x\in[0,1)[/inlmath] kod integracije.

@Onomatopeja

Svaka čast, nekako sam pretpostavio da ćeš rešavati zadatak preko integrala...

Nije mi baš jasan postupak, kako izvesti [inlmath]\frac{1}{k}=\int\limits_0^1t^{k-1}\mathrm dt[/inlmath] i [inlmath]\sum\limits_{k=1}^n{n\choose k}(-1)^{k+1}t^{k-1}=\frac{1-(1-t)^n}{t}[/inlmath]

Obe te jednakosti smo koristili sleva udesno, te sam ih zbog toga i tako zapisao. Ali, da bismo ih pokazali, trebalo bi da ih citamo zdesna ulevo. Za prvu jednakost, ako tako posmatramo celu situaciju, izracunaj integral. Za drugu, razvij [inlmath](1-t)^n[/inlmath] preko binomne formule, pa onda sredi sve.

Da li je ovo korektan dokaz indukcijom:

Za [inlmath]n=1[/inlmath] jednakost je tačna.

Za [inlmath]n=m[/inlmath]
[dispmath]\sum_{k=1}^m(-1)^{k+1}{m\choose k}\frac{1}{k}=1+\frac{1}{2}+\cdots+\frac{1}{m}[/dispmath]
Za [inlmath]n=m+1[/inlmath]
[dispmath]\sum_{k=1}^{m+1}(-1)^{k+1}{m+1\choose k}\frac{1}{k}=1+\frac{1}{2}+\cdots+\frac{1}{m+1}[/dispmath]
Dokaz:
[dispmath]\sum_{k=1}^m(-1)^{k+1}{m\choose k}\frac{1}{k}+(-1)^{2(m+1)}\frac{1}{m+1}[/dispmath]
što je tačno.

Da malo odmenim Onomatopeju, zaista se čovek naradio, obavio je glavni deo posla...

EDIT: Ups, tek sad videh da postoji i ova druga stranica teme, u kojoj je čovek već objasnio kako se radi, al' kad sam već sve ovo napisao, šteta da se baci...

[inlmath]\frac{1}{k}[/inlmath] možeš napisati na sledeći način:
[dispmath]\frac{1}{k}=\frac{1}{k}\left(1^k-0^k\right)=\left.\frac{1}{k}\cdot t^k\right|_0^1=\frac{1}{k}\int\limits_0^1\left(t^k\right)'\mathrm dt=\frac{1}{\cancel k}\int\limits_0^1\cancel kt^{k-1}\mathrm dt=\int\limits_0^1t^{k-1}\mathrm dt[/dispmath]
[inlmath]\sum\limits_{k=1}^n{n\choose k}\left(-1\right)^{k+1}t^{k-1}[/inlmath] možeš uporediti s binomnom formulom:
[dispmath]\left(a+b\right)^n=\sum_{k=0}^n{n\choose k}a^{n-k}b^k[/dispmath]
Svedemo formulu [inlmath]\sum\limits_{k=1}^n{n\choose k}\left(-1\right)^{k+1}t^{k-1}[/inlmath] na oblik koji će malo više ličiti binomnoj formuli. Prvo, [inlmath]t^{k-1}[/inlmath] pišemo kao [inlmath]\frac{1}{t}\cdot t^k[/inlmath], pri čemu [inlmath]\frac{1}{t}[/inlmath] može izaći ispred sume:
[dispmath]\sum_{k=1}^n{n\choose k}\left(-1\right)^{k+1}t^{k-1}=\frac{1}{t}\sum_{k=1}^n{n\choose k}\left(-1\right)^{k+1}t^k[/dispmath]
Takođe, vidimo da suma ide od [inlmath]1[/inlmath] do [inlmath]n[/inlmath], a kod binomne formule ide od [inlmath]0[/inlmath] do [inlmath]n[/inlmath]. Zato dodamo i oduzmemo taj nulti član:
[dispmath]\frac{1}{t}\sum_{k=1}^n{n\choose k}\left(-1\right)^{k+1}t^k=\frac{1}{t}\sum_{k=0}^n{n\choose k}\left(-1\right)^{k+1}t^k-\frac{1}{t}{n\choose 0}\left(-1\right)^{0+1}t^0=\frac{1}{t}\sum_{k=0}^n{n\choose k}\left(-1\right)^{k+1}t^k+\frac{1}{t}[/dispmath]
Pošto je u binomnoj formuli jedan član dignut na [inlmath]k[/inlmath], a drugi na [inlmath]n-k[/inlmath], a mi ovde već imamo jedan član ([inlmath]t[/inlmath]) dignut na [inlmath]k[/inlmath], to znači da drugi član ([inlmath]-1[/inlmath]) treba nekako da dignemo na [inlmath]n-k[/inlmath]. Sad ovde imamo dva slučaja. Za [inlmath]n[/inlmath] parno, biće [inlmath]\left(-1\right)^{k+1}=-\left(-1\right)^{n-k}[/inlmath], dok će za [inlmath]n[/inlmath] neparno biti [inlmath]\left(-1\right)^{k+1}=\left(-1\right)^{n-k}[/inlmath].

[inlmath]n[/inlmath] parno:
[dispmath]\frac{1}{t}\sum_{k=0}^n{n\choose k}\left(-1\right)^{k+1}t^k+\frac{1}{t}=-\frac{1}{t}\sum_{k=0}^n{n\choose k}\left(-1\right)^{n-k}t^k+\frac{1}{t}=-\frac{1}{t}\left(-1+t\right)^n+\frac{1}{t}=\frac{1-\left(1-t\right)^n}{t}[/dispmath]
Naravno, [inlmath]\left(-1+t\right)^n[/inlmath] je isto što i [inlmath]\left(1-t\right)^n[/inlmath], budući da je [inlmath]n[/inlmath] parno.

[inlmath]n[/inlmath] neparno:
[dispmath]\frac{1}{t}\sum_{k=0}^n{n\choose k}\left(-1\right)^{k+1}t^k+\frac{1}{t}=\frac{1}{t}\sum_{k=0}^n{n\choose k}\left(-1\right)^{n-k}t^k+\frac{1}{t}=\frac{1}{t}\left(-1+t\right)^n+\frac{1}{t}=\frac{1-\left(t-1\right)^n}{t}[/dispmath]
i dolazimo do istog rezultata i za [inlmath]n[/inlmath] parno i za [inlmath]n[/inlmath] neparno, te je ovime pokazano da je
[dispmath]\sum_{k=1}^n{n\choose k}\left(-1\right)^{k+1}t^{k-1}=\frac{1-\left(t-1\right)^n}{t}[/dispmath]

display_error je napisao:Da li je ovo korektan dokaz indukcijom:
[inlmath]\vdots[/inlmath]
Dokaz:
[dispmath]\sum_{k=1}^m(-1)^{k+1}{m\choose k}\frac{1}{k}+(-1)^{2(m+1)}\frac{1}{m+1}[/dispmath]
što je tačno.

Na koji način si došao do ovog izraza?

Da bi se iskoristila induktivna pretpostavka (u dokazu):
[dispmath]\sum_{k=1}^m(-1)^{k+1}{m\choose k}\frac{1}{k}[/dispmath]
Na ovo dodamo deo induktivnog koraka [inlmath]\sum\limits_{k=m+1}^{m+1}(-1)^{k+1}{m+1\choose k}\frac{1}{k}=(-1)^{m+2}\frac{1}{m+1}[/inlmath]

E sad pošto je sa desne strane (u dokazu) sabirak [inlmath]\frac{1}{m+1}[/inlmath] pozitivan, postavio sam [inlmath](-1)^{m+2}\frac{1}{m+1}[/inlmath] na [inlmath](-1)^{2(m+1)}\frac{1}{m+1}[/inlmath]

Znam da ovo nije korektno, ali pokušao sam da rešim zadatak indukcijom.

Hvala na detaljnom pojašnjenju.

display_error je napisao:Da bi se iskoristila induktivna pretpostavka (u dokazu):
[dispmath]\sum_{k=1}^m(-1)^{k+1}{m\choose k}\frac{1}{k}[/dispmath]
Na ovo dodamo deo induktivnog koraka [inlmath]\sum\limits_{k=m+1}^{m+1}(-1)^{k+1}{m+1\choose k}\frac{1}{k}=(-1)^{m+2}\frac{1}{m+1}[/inlmath]

Nisam siguran jesam li dobro razumeo šta je bila tvoja ideja, ali ne možeš na [inlmath]\sum\limits_{k=1}^m\left(-1\right)^{k+1}{{\color{red}m}\choose k}\frac{1}{k}[/inlmath] da dodaješ [inlmath]\sum\limits_{k=m+1}^{m+1}\left(-1\right)^{k+1}{m+1\choose k}\frac{1}{k}[/inlmath], budući da suma prvih [inlmath]m[/inlmath] članova induktivnog koraka ne glasi [inlmath]\sum\limits_{k=1}^m\left(-1\right)^{k+1}{{\color{red}m}\choose k}\frac{1}{k}[/inlmath], već glasi [inlmath]\sum\limits_{k=1}^m\left(-1\right)^{k+1}{{\color{red}m+1}\choose k}\frac{1}{k}[/inlmath].

display_error je napisao:E sad pošto je sa desne strane (u dokazu) sabirak [inlmath]\frac{1}{m+1}[/inlmath] pozitivan, postavio sam [inlmath](-1)^{m+2}\frac{1}{m+1}[/inlmath] na [inlmath](-1)^{2(m+1)}\frac{1}{m+1}[/inlmath]

To što je [inlmath]\frac{1}{m+1}[/inlmath] pozitivan, nema nikakve veze s tim da mora i [inlmath]\left(-1\right)^{m+2}[/inlmath] biti pozitivno, to su dva odvojena činioca.
Drugo, ne smeš u indukciji da „štimuješ“ vrednost [inlmath]m[/inlmath]. Indukcija je vrlo jasna – treba dokazati da, ako nešto važi za [inlmath]m[/inlmath], tada važi i za [inlmath]m+1[/inlmath].