Podzielność silni

[Thingoln]

Witajcie. Mam kolejne zadanie z teorii liczb do rozwiązania. Na początek podam treść zadania i napiszę, co udało mi się do tej pory zrobić.

Dowieść, że \(\displaystyle{ 2^n \nmid n!}\) dla \(\displaystyle{ n \in \mathbb{N_{+}}}\).

\(\displaystyle{ 2^n \nmid n! \Leftrightarrow n \nmid v_p (n)}\)

Ze wzoru Legendre'a wynika również, że jest to równoważne
\(\displaystyle{ n \nmid \left\lfloor \frac{n}{2}\right\rfloor + \left\lfloor \frac{n}{2^2}\right\rfloor + \cdots + \left\lfloor \frac{n}{2^k}\right\rfloor \ \ (1)}\),
gdzie \(\displaystyle{ 2^k \le n < 2^{k+1}}\) i \(\displaystyle{ k \in \mathbb{N_{+}}}\).

I tutaj pojawia się moje pytanie. Czy można uzasadnić \(\displaystyle{ (1)}\) w ten sposób?

Weźmy pod uwagę ciąg geometryczny \(\displaystyle{ (a_m)}\) określony wzorem \(\displaystyle{ a_m = \frac{n}{2} \cdot \left(\frac{1}{2}\right)^{m-1}}\). Oznaczmy jego iloraz jako \(\displaystyle{ q}\). Oczywiście jest on równy \(\displaystyle{ \frac{1}{2}}\), a więc \(\displaystyle{ |q| < 1}\). Wynika z tego, że istnieje skończona wartość szeregu \(\displaystyle{ \sum_{m=1}^{ \infty} a_m}\) równa \(\displaystyle{ a_1 \cdot \frac{1}{1-q} = \frac{n}{2} \cdot \frac{1}{1-\left(\frac{1}{2}\right)} = \frac{n}{2} \cdot \frac{1}{\frac{1}{2}} = n}\).
Dla dowolnej liczby naturalnej dodatniej \(\displaystyle{ t}\) wyraz \(\displaystyle{ a_t}\) jest liczbą dodatnią. Stąd suma \(\displaystyle{ t}\) pierwszych wyrazów tego ciągu jest funkcją ściśle rosnącą. Zauważmy również, że dla dowolnej liczby rzeczywistej \(\displaystyle{ x}\) zachodzi \(\displaystyle{ x-1 < \left\lfloor x \right\rfloor \le x}\), więc także
\(\displaystyle{ \left\lfloor \frac{n}{2}\right\rfloor + \left\lfloor \frac{n}{2^2}\right\rfloor + \cdots + \left\lfloor \frac{n}{2^k}\right\rfloor \le \frac{n}{2} + \frac{n}{2^2} + \cdots + \frac{n}{2^k}}\)

Dla dowolnej liczby naturalnej dodatniej \(\displaystyle{ t}\) zachodzi więc
\(\displaystyle{ 0 \le \sum_{m=1}^{t} \left\lfloor a_m \right\rfloor \le \sum_{m=1}^{t} a_m < \sum_{m=1}^{\infty} a_m = n}\),
więc \(\displaystyle{ (1)}\) jest spełnione, bo większa liczba naturalna nie może dzielić mniejszej różnej od zera.

[Premislav]

\(\displaystyle{ 2^n \nmid n! \Leftrightarrow n \nmid v_p (n)}\)

Hmm? No nie bardzo. Trochę pomieszałeś. Raczej dla dowolnej liczby pierwszej \(\displaystyle{ p}\) będzie \(\displaystyle{ p^{n}\nmid n!\Leftrightarrow v_{p}(n!)<n}\) i dalej wszak wyliczasz i szacujesz z góry \(\displaystyle{ v_{2}(n!)}\).
I znów, dalej:

Ze wzoru Legendre'a wynika również, że jest to równoważne
\(\displaystyle{ n \nmid \left\lfloor \frac{n}{2}\right\rfloor + \left\lfloor \frac{n}{2^2}\right\rfloor + \cdots + \left\lfloor \frac{n}{2^k}\right\rfloor }\)
gdzie \(\displaystyle{ 2^k \le n < 2^{k+1}}\) i \(\displaystyle{ k\in \NN_{+}}\)

No nie, jest to równoważne nierówności \(\displaystyle{ n> \left\lfloor \frac{n}{2}\right\rfloor + \left\lfloor \frac{n}{2^2}\right\rfloor + \cdots + \left\lfloor \frac{n}{2^k}\right\rfloor}\), gdzie \(\displaystyle{ 2^{k}\le n<2^{k+1}}\).
Samo szacowanie z góry \(\displaystyle{ v_{2}(n!)}\) jest natomiast całkowicie poprawne.

[Thingoln]

Aj, rzeczywiście tutaj się zagapiłem. Oczywiście zgadzam się. W takim razie jest to poprawne rozwiązanie po naniesieniu Twoich poprawek?

[Premislav]

Jak najbardziej.

[Thingoln]

Dziękuję za pomoc. Mam jeszcze pytanie, czy dałoby się to udowodnić w inny sposób? Może jakiś bardziej „typowy” dla teorii liczb.

[Premislav]

Nie żebym był specjalistą od teorii liczb, ale moim zdaniem ten sposób jest dla niej bardzo typowy. Trudno mi sobie wyobrazić inne rozwiązanie (może mam małą wyobraźnię ), ale też bym chętnie takie zobaczył, bo inaczej nie umiem.

[pasman]

Można zastosować indukcję matematyczną. Rozłóżmy silnię na iloczyn.

\(\displaystyle{ n! = n!! \cdot (n-1)!!}\)

Jeżeli \(\displaystyle{ n}\) jest nieparzyste to \(\displaystyle{ n!!}\) nie dzieli się przez \(\displaystyle{ 2}\) i interesuje nas tylko \(\displaystyle{ (n-1)!!}\).

Jeżeli \(\displaystyle{ n}\) jest parzyste to zapisujemy \(\displaystyle{ n!! = 2^{n/2} \cdot (n/2)! }\)
Wstawiając do wcześniejszej zależności dostajemy tezę dla mniejszego \(\displaystyle{ n}\) :

\(\displaystyle{ 2^{n/2} \nmid (n/2)!}\).

Kontynuując dalej dostajemy sprzeczność:

\(\displaystyle{ 2^1 \nmid 1!}\).

[Bran]

A ja może tak z ciekawości zapytam: Co to jest \(\displaystyle{ v_p\left( n\right) }\)?

[Premislav]

Dla liczby pierwszej \(\displaystyle{ p}\) i \(\displaystyle{ n\in \ZZ\setminus \left\{0\right\}}\) mówimy, że \(\displaystyle{ v_{p}(n)=x}\), gdy
\(\displaystyle{ p^{x}|n, \ p^{x+1} \nmid n}\).

[Thingoln]

pasmanie, dzięki za Twoje rozwiązanie! Wygląda ciekawie, chociaż na końcu chyba zamiast sprzeczności jest spełnienie tezy. W każdym razie świetnie poznać jeszcze inne podejście do tego zadania.

[Bran]

To ja zaproponuję coś swojego.

Zauważmy, że aby \(\displaystyle{ 2^n}\) dzieliło \(\displaystyle{ n!}\), to \(\displaystyle{ n!}\) musi mieć w swoim rozkładzie conajmniej \(\displaystyle{ n}\) dwójek.

Weźmy \(\displaystyle{ n}\) kolejnych liczb i oszacujmy ile łącznie dwójek w nich występuje.

Oczywistym oszacowaniem z góry jest: \(\displaystyle{ \frac{n}{2} + \frac{n}{2^2}+ \frac{n}{2^3}+ \frac{n}{2^4} + \dots + \frac{n}{2^n}}\)

Wystarczy więc wykazać, że:
\(\displaystyle{ \frac{n}{2} + \frac{n}{2^2}+ \frac{n}{2^3}+ \frac{n}{2^4} + \dots + \frac{n}{2^n} \ge n}\)
Po podzieleniu obustronnie przez \(\displaystyle{ n}\) mamy \(\displaystyle{ \frac{1}{2} + \frac{1}{2^2}+ \frac{1}{2^3}+ \frac{1}{2^4} + \dots + \frac{1}{2^n} \ge 1}\)
A to jest sprzeczne, bo \(\displaystyle{ \sum_{n=1}^\infty \frac{1}{2^n} = 1.}\)