saas Mateusz: Witam mógłby ktoś mi pomóc udowodnic tozsamosci kombinatoryczne?

	n k
1.∑nk=1k		=n2n−1

	n 2		n+1 2
2.∑nk=1(2k−1)=		+

	n+1 2
3.∑nk=1k3=		2

Pan doktor powiedział, że jedno z tych tozsamosci jest w podreczniku Analiza Kombinatoryczna(Marek Wiktor), ale niestety nie moge tego dowodu znalezc...

Adamm:

	n k		n−1 k−1
1. k		=n		i dwumian Newtona

Mateusz: Adamm , dowody trzeba uzasadnic kombinatorycznie

Adamm:

	k 1		k−1 1
2. ∑k=1n2k−1=∑k=1n		+∑k=2n

k 1

1 1

2 1

n 1

2 2

2 1

n 1

∑k=1n

=

+

+...+

=

+

+...+

=

3 2

3 1

n 1

n 2

n 1

n+1 2

=

+

+...+

=...=

+

=

tak samo

	k−1 1		n 2
∑k=2n		=

stąd

	n 2		n+1 2
∑k=1n2k−1=		+

Mateusz: Adamm wiem ze to co piszesz jest dobrze. Ale Pan doktor kazał udowodnic to na przykladzie podzbiorow, ciagow, elementow minimalnych itd.

Mateusz: czyli pisemnie gdzie wyjasnienie tego bedzie

Mateusz: ktoś coś ? Czy tak może być? Weźmy Prawą stronę tozsamosci n*2ⁿ⁻¹ Niech X={a_i,...,a_n} gdzie i={1,..,n} 1. Wybierzmy dokladnie jeden element a_i bez zwracania ze Zbioru X − mamy na to n sposobow. 2. Z powstałego zbioru X\a_i utworzmy wszystkie podzbiory Z − mamy na to 2ⁿ⁻¹ sposobów bo tyle jest podzbiorow zbioru liczącego n−1 elementow. Korzystajać z reguły mnożenia ostatecznym wynikiem jest n*2ⁿ⁻¹ . A jak ugryźć to z prawej strony?

Mateusz: pomoze ktos?

jc: (1) Ile elementów mają razem wszystkie podzbiory zbioru n elementowego? Liczymy na dwa sposoby. Suma po lewej stronie jest oczywista. Prawa strona. Każdy element należy do połowy podzbiorów, a wiec razem mamy n2ⁿ⁻¹. Stąd równość.