szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 cze 2014, o 12:46 
Użytkownik

Posty: 53
Lokalizacja: Gdańsk
Witam,

proszę o rozwiązanie zadania, próbowałem to przepałować na liczeniu dwójek w silni za pomocą wzoru stąd http://pl.wikipedia.org/wiki/Silnia#Rozk.C5.82ad_silni_na_czynniki_pierwsze, ale nie wyszło mi na razie :)

Udowodnić, że jeżeli 0<k<2^n, to 2| {2^n \choose k}
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2014, o 13:55 
Użytkownik

Posty: 254
Lokalizacja: Polska
Mam całkiem fajny sposób na udowodnienie z pomocą interpretacji symbolu newtona za pomocą trójkąta Pascala. Masz to wykazania, że w każdym jego wierszu postaci 2^{n} są (poza skrajnymi jedynkami) same wyrazy parzyste. Rozważ konstrukcję trójkąta Pascala tylko pod względem parzystości wyrazów i przeprowadź dowód indukcyjny (nie wiem czy to najlepszy dowód ale na pewno ciekawy).
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2014, o 14:18 
Użytkownik

Posty: 9836
Lokalizacja: Bydgoszcz
W rozkład (2^n)! na czynniki pierwsze dwójka wchodzi z wykładnikiem:
\sum_{i\ge 0}\left\lfloor \frac{2^n}{2^i}\right\rfloor =\sum_{i=0}^n \left\lfloor \frac{2^n}{2^i}\right\rfloor =\sum_{i=0}^n\frac{2^n}{2^i} =1+\sum_{i=0}^{n-1}\frac{2^n}{2^i}
natomiast w rozkład k! z wykładnikiem:
\sum_{i\ge 0}\left\lfloor \frac{k}{2^i}\right\rfloor
oraz w rozkład (2^n-k)! z wykładnikiem:
\sum_{i\ge 0}\left\lfloor \frac{2^n-k}{2^i}\right\rfloor

Zauważmy jednak, że z uwagi na k<2^n i 2^n-k<2^n w dwóch ostatnich sumach składnik dla i=n będzie się zerował, stąd wystarczy jak ostatnim indeksem sumowania będzie n-1. Stąd mamy szacowanie na wykładnik dwójki z jakim wchodzi ona w rozkład k!\cdot (2^n-k)! na czynniki pierwsze:
\sum_{i= 0}^{n-1}\left\lfloor \frac{k}{2^i}\right\rfloor + \sum_{i= 0}^{n-1}\left\lfloor \frac{2^n-k}{2^i}\right\rfloor \le 
\sum_{i= 0}^{n-1} \frac{k}{2^i} + \sum_{i= 0}^{n-1} \frac{2^n-k}{2^i}= \sum_{i=0}^{n-1}\frac{2^n}{2^i}
co oczywiście jest o jeden mniejsze niż wykładnik dwójki w rozkładzie (2^n)!, co kończy dowód.

Q.
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2014, o 16:35 
Użytkownik

Posty: 53
Lokalizacja: Gdańsk
Ładne, dziękuję :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Suma trzech kolejnych potęg dwójki - podzielność przez 14.  krzysiu184  3
 Zadanie z podzielności- suma potęg dwójki  nn  2
 Co oznacza ten symbol?  mgl24  2
 potega liczb  martynka148  1
 Potęga dwójki - zadanie 2  zyd  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl