indukcja ania: (m+n) po k =∑(m po i)*(n po (k−i)) wzgledem n k ∑ i=0 Prosze o szybka pomoc, ostanie zadanie domowe ktore nie moglam zrobic a cwiczenia mam za poltorej godziny.

Basia:

m+n k		m i		n k−1
	= ∑i=0,...,k		*

widzisz jakie to proste

Vax:

m+n k		m i	n k−i
	= ∑i=0k

Załóżmy, że mamy m chłopców, n dziewczynek i chcemy wybrać drużynę składającą się z k osób. Z

	m+n k
jednej strony możemy to zrobić na		sposobów. Z drugiej strony, możemy zrobić tak, że

	m i
na początku wybieramy i chłopaków (na		sposobów), a potem dokładamy do tego k−i

	n k−i
dziewczynek (na		sposobów), dla i=0,1,2,...,k. Można to zrobić na:

	m i	n k−i
∑i=0k			sposobów, cnd.

Vax: Co ciekawe, można zauważyć, że dane rozumowanie można uogólnić dostając taki ciekawy wzór:

a1+a2+...+an k		a1 b1	a2 b2		an bn
	= ∑b1+b2+...+bn = k , bi ≥ 0			...

ania: Czyli to juz jest jakby udowodnione? nie mam tego rozpisywac zakladac ze n+1 itd?

Vax: Tak, to jest tzw. dowód kombinatoryczny, najszybszy i najpiękniejszy Bardzo często ciężko jest dowieść pewnej tożsamości algebraicznie, a wymyślając odpowiednią historyjkę dostajemy dowód na 2 linijki.