Matematyka dyskretna Kalasznikov: Witam, przychodzę z prośbą wykonania następującego zadania z matematyki dyskretnej: https://iv.pl/image/Grze53p Z góry dziękuję.

Blee: 1) zacząć należy od wykazania, że:

	n k
2n = ∑0n

	n k
wykorzystamy do tego wzór (a+b)n = ∑0n		akbn−k

gdy podstawimy a = b = 1 to otrzymamy powyższą równość 2)

	n k		n n−k
zauważamy, że		=

n n−k

n n−k

n k

n

n k

n n−k

więc k*

+ (n−k)*

= n*

=

(

+

)

2

i zachodzi to dla dowolnego k ≤ n 3) więc ... jeżeli mamy n = 2j+1 (liczba nieparzysta)

	n k		n	n k		n
to ∑0n k		= ∑			=		*2n = n2n−1
			2			2

4) jeżeli natomiast n = 2j (liczba parzysta) to występuje wyraz 'środkowy'

	n
innymi słowy, dla k ≠		mamy to samo co powyżej
	2

	n		n		n n/2
natomiast dla k =		mamy po prostu		*		co także nam się pięknie składa 'do
	2		2

kupy' dodajesz odpowiednią opisówkę i gotowe Tak −−− to jest ZARYS dowodu. Musisz jeszcze go 'dopieścić'.

jc: To suma liczb elementów we wszystkich podzbiorach zbioru n elementowego. Dla n>0 każdy element należy do połowy podzbiorów, a ponieważ mamy n elementów, więc suma = n*2ⁿ/2=n2ⁿ⁻¹.