Dowodzenie prawdziwości, silnie iksa: Udowodnij, że dla dowolnej liczby całkowitej dodatniej n liczba (2n)! jest podzielna przez (n!)²

Gray: Można inaczej, ale proponuję dowód indukcyjny − będzie łatwo i przyjemnie

iksa: (2n)! = (n!)² * k ?

Gray: Tak, k=k(n) tj. k zależy od n. To spróbuj udowodnić indukcyjnie.

iksa: 1. Dla n=1 L=2 P=1 * k , więc dla k=2 tak ?

Gray: Tak.

Gray:

	n k
Gdybyś się poddał (czego nie polecam) − jest alternatywa Wiemy, że dla n≥k liczba		to

liczba k−elementowych podzbiorów zbioru n−elementowego; jest to więc liczba całkowita. Taką

	2n n
liczbę jest więc również		− liczba n−elementowych podzbiorów zbioru 2n−elementowego.

	2n n		(2n)!
Ale		=		, więc ... Koniec
			(n!)2

iksa: dzięki

zombi: Ew. można próbować w ten sposób. Skoro (n!)²|(2n)!, to n! | (2n)(2n−1)*...*(n+2)(n+1). Trzeba pokazać, że wśród liczb A={n+1,n+2,..., 2n−1, 2n} znajduje się wielokrotność każdej z liczb B={1,2,...,n}. Musimy rozpatrzeć przystawanie modulo, każdej liczby ze zbioru A modulo B Przykładowo, sprawdźmy czy w zbiorze A istnieje wielokrotność 7. Załóżmy, że n+1 ≡ 1 (mod 7) n+2 ≡ 2 (mod 7) . . . n+7 ≡ 0 (mod 7). Czyli znajdziemy wielokrotność 7 wśród liczb zbioru A. Ogólnie dla każde liczby ze zbioru B znajdziemy jej wielokrotność wśród liczb ze zbioru A, bo każda k−ta liczba (z zb. B) daje k możliwych reszt z dzielenia od 0,1,...,k−1, a jak wiadomo w zbiorze A jest n kolejnych liczb naturalnych, więc koniec końców musimy trafić na wielokrotność liczby ze zbioru B. To chyba wynika z zasady szufladkowej Dirichleta, jeśli szufladkami będą możliwe reszty z dzielenia przez k. tj {0,1,...,k−1}. Ew. jeśli to jest złe rozwiązanie, można próbować z wykorzystaniem funkcji

	n
αp(n!) = ∑[		] Gdzie ap(n!) to wykładnik przy liczbie pierwszej p w rozkładzie n! na
	pk

czynniki pierwszej a [ ] − to podłoga. Takie luźne dygresje

zombi: Tam źle napisałem, każda liczba ze zbioru A daje k możliwych reszt z dzielenia przez liczbę k, ze zbioru B a nie na odwrót. Bo ogólnie rozpatrujemy jakaś tam liczby p∊A modulo liczby k∊B, a jak wiadomo p ≡ r (mod k), gdzie r={0,1,...,k−1}.

zombi:

	n k
Ale Gray podał najszybszy sposób, wiedząc, że		jest naturalna, co polecam udowodnić,

	2n n
natychmiast mamy tezę biorąc

iksa: zombi Twoje rozwiązanie to jeszcze nie mój poziom