Potrebna mi je pomoć oko sledećeg zadatka:
Dokazati jednakost
[dispmath]\sum_{k=m}^n{n\choose k}{k\choose m}={n\choose m}2^{n-m}[/dispmath]
Može li neko detaljno da pojasni da li se radi o čistoj indukciji (uz binomnu formulu) ili se jednakost dokazuje na drugi način?
Index stranica ‹ OSTALE MATEMATIČKE OBLASTI ‹ KOMBINATORIKA
Dokazati jednakost – suma s binomnim koeficijentima
Pregled za štampanje • Pregled za štampanje svih postova u temi • 5 Posta
• Stranica 1 od 1
Re: Dokazati jednakost – suma s binomnim koeficijentima
od Daniel » Petak, 26. Jun 2015, 01:45
Ne vidim načina da se ovo uradi preko indukcije. Situaciju komplikuje to što unutar same sume figuriše [inlmath]m[/inlmath], koje je ujedno i donja granica sume.
Pokušaj ovako (meni je pošlo za rukom): izraz unutar sume, [inlmath]{n\choose k}{k\choose m}[/inlmath], transformiši tako da dobiješ proizvod binomnog koeficijenta [inlmath]n\choose m[/inlmath] (koji može izaći ispred sume jer u njemu ne figuriše [inlmath]k[/inlmath]) i drugog binomnog koeficijenta u kojem [inlmath]k[/inlmath] figuriše. Za sumu koju dobiješ na taj način lako možeš pokazati da je jednaka [inlmath]2^{n-m}[/inlmath], koristeći svojstvo [inlmath]\sum\limits_{k=0}^n{n\choose k}=2^n[/inlmath].
Pokušaj ovako (meni je pošlo za rukom): izraz unutar sume, [inlmath]{n\choose k}{k\choose m}[/inlmath], transformiši tako da dobiješ proizvod binomnog koeficijenta [inlmath]n\choose m[/inlmath] (koji može izaći ispred sume jer u njemu ne figuriše [inlmath]k[/inlmath]) i drugog binomnog koeficijenta u kojem [inlmath]k[/inlmath] figuriše. Za sumu koju dobiješ na taj način lako možeš pokazati da je jednaka [inlmath]2^{n-m}[/inlmath], koristeći svojstvo [inlmath]\sum\limits_{k=0}^n{n\choose k}=2^n[/inlmath].
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Re: Dokazati jednakost – suma s binomnim koeficijentima
od desideri » Petak, 26. Jun 2015, 12:39
Indukciju zaboravi, molim te.
Evo još jedne ideje, pored ove Danielove.
Ja bih doveo red "u red"
To znači da ide od nule.
Postižem to smenom [inlmath]z=k-m[/inlmath].
Dobijam:
[dispmath]\sum_{z=0}^{n-m}{n\choose z+m}{z+m\choose m}[/dispmath]
Posle pretvaranja binomnih koeficijenata u faktorijele jako brzo sam dobio rezultat.
Evo još jedne ideje, pored ove Danielove.
Ja bih doveo red "u red"
To znači da ide od nule.
Postižem to smenom [inlmath]z=k-m[/inlmath].
Dobijam:
[dispmath]\sum_{z=0}^{n-m}{n\choose z+m}{z+m\choose m}[/dispmath]
Posle pretvaranja binomnih koeficijenata u faktorijele jako brzo sam dobio rezultat.
Re: Dokazati jednakost – suma s binomnim koeficijentima
od Daniel » Petak, 26. Jun 2015, 17:55
desideri je napisao:Postižem to smenom [inlmath]z=k-m[/inlmath].
Ova smena u svakom slučaju ne gine, bez obzira na to da l' se radi na „tvoj“ ili na „moj“ način.
Kod mene se smena uvodi nakon transformacije izraza pod sumom i izvlačenja jednog binomnog koeficijenta ispred sume, a kod tebe se prvo uvodi smena, pa se tek onda izraz transformiše.
U principu, vrlo su nam slični načini, samo je redosled postupaka drugačiji.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Re: Dokazati jednakost – suma s binomnim koeficijentima
od display_error » Petak, 26. Jun 2015, 19:16
Uradio sam zadatak, nisam koristio smene. Levu stranu sam razvio i faktorisao u obliku
[dispmath]\frac{n!}{m!}\left(\frac{1}{0!(n-m)!}+\frac{1}{1!\big(n-(m+1)\big)!}+\cdots+\frac{1}{(n-m)!}\right)[/dispmath]
Isti se izraz dobija sa desne strane korišćenjem binomne formule za [inlmath](1+1)^{n-m}[/inlmath] i izvlačenjem [inlmath]\frac{n!}{m!}[/inlmath] ispred zagrade.
[dispmath]\frac{n!}{m!}\left(\frac{1}{0!(n-m)!}+\frac{1}{1!\big(n-(m+1)\big)!}+\cdots+\frac{1}{(n-m)!}\right)[/dispmath]
Isti se izraz dobija sa desne strane korišćenjem binomne formule za [inlmath](1+1)^{n-m}[/inlmath] i izvlačenjem [inlmath]\frac{n!}{m!}[/inlmath] ispred zagrade.
Poslednji put menjao desideri dana Petak, 26. Jun 2015, 20:13, izmenjena samo jedanput
Razlog: Ispravka slovne greške u kucanju.
Razlog: Ispravka slovne greške u kucanju.
5 Posta
• Stranica 1 od 1
Ko je OnLine
Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 20 gostiju