szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 8 paź 2016, o 09:54 
Użytkownik

Posty: 39
Lokalizacja: Polska
Witam. Piszę o pewnej właściwości, którą zauważyłem w trójkącie Pascala, a mianowicie, że

(a + n + 1) \cdot {{a + n} \choose a} jest podzielne przez a + 1

Tu jest dowód (gdyby ktoś zauważył jakiś błąd, to proszę o napisanie):

Na początku założymy, że:

[a + (n - 1) + 1] \cdot {{a + (n - 1)} \choose a} \equiv 0 \pmod{a + 1}

Czyli, że właściwość się sprawdza dla n zmniejszonego o 1. Teraz pokażemy, że:

(a + n + 1) \cdot {{a + n} \choose a} \equiv 0 \pmod{a + 1}

musi być prawdą. Przekształcamy:

(a + n + 1) \cdot {{a + n} \choose a} \equiv 0 \pmod{a + 1}

(a + n) \cdot {{a + n} \choose a} + {{a + n} \choose a} \equiv 0 \pmod{a + 1}

[a + (n - 1) + 1] \cdot \Biggl({{a + n - 1} \choose a} + {{a + n - 1} \choose a - 1}\Biggr) + {{a + n - 1} \choose a} + {{a + n - 1} \choose a - 1} \equiv 0 \pmod{a + 1}

[a + (n - 1) + 1] \cdot {{a + n - 1} \choose a} + [a + (n - 1) + 1] \cdot {{a + n - 1} \choose a - 1} + {{a + n - 1} \choose a} + {{a + n - 1} \choose a - 1} \equiv 0 \pmod{a + 1}

[a + (n - 1) + 1] \cdot {{a + (n - 1)} \choose a} + (a + n + 1) \cdot {{a + n - 1} \choose a - 1} + {{a + n - 1} \choose a} \equiv 0 \pmod{a + 1}

W tym momencie (zgodnie z pierwszym założeniem) możemy ze wzoru wyrzucić wyraz [a + (n - 1) + 1] \cdot {{a + (n - 1)} \choose a} i przekształcać dalej:

(a + n + 1) \cdot {{a + n - 1} \choose a - 1} + {{a + n - 1} \choose a} \equiv 0 \pmod{a + 1}

(a + 1) \cdot {{a + n - 1} \choose a - 1} + n \cdot {{a + n - 1} \choose a - 1} + {{a + n - 1} \choose a} \equiv 0 \pmod{a + 1}

Teraz wyrzucamy wyraz (a + 1) \cdot {{a + n - 1} \choose a - 1} bo, rzecz jasna, jest podzielny przez a + 1 i od razu przekształcamy dwumiany Newtona:

n \cdot \frac{(a + n - 1)!}{(a - 1)! \cdot [a + n - 1 - (a - 1)]!} + \frac{(a + n - 1)!}{a! \cdot (a + n - 1 - a)!} \equiv 0 \pmod{a + 1}

n \cdot \frac{(a + n - 1)!}{(a - 1)! \cdot n!} + \frac{(a + n - 1)!}{a! \cdot (n - 1)!} \equiv 0 \pmod{a + 1}

\frac{(a + n - 1)!}{(n - 1)!} \cdot \Bigl(\frac{1}{(a - 1)!} + \frac{1}{a!}\Bigr) \equiv 0 \pmod{a + 1}

\frac{(a + n - 1)!}{(n - 1)!} \cdot \Bigl(\frac{a}{a!} + \frac{1}{a!}\Bigr) \equiv 0 \pmod{a + 1}

\frac{(a + n - 1)!}{(n - 1)! \cdot a!} \cdot (a + 1) \equiv 0 \pmod{a + 1}

\frac{(a + n - 1)!}{(a + n - 1 - a)! \cdot a!} \cdot (a + 1) \equiv 0 \pmod{a + 1}

{{a + n - 1} \choose a} \cdot (a + 1) \equiv 0 \pmod{a + 1}

I w ten sposób otrzymaliśmy, że przy założeniu, że:

[a + (n - 1) + 1] \cdot {{a + (n - 1)} \choose a} \equiv 0 \pmod{a + 1}

Prawdą musi być:

(a + n + 1) \cdot {{a + n} \choose a} \equiv 0 \pmod{a + 1}

Na koniec jeszcze w takim razie wystarczy udowodnić, że wzór jest prawdziwy dla n = 0 :

(a + 0 + 1) \cdot {{a + 0} \choose a} \equiv 0 \pmod{a + 1}

(a + 1) \cdot 1 \equiv 0 \pmod{a + 1}

a + 1 \equiv 0 \pmod{a + 1}

I to jest prawdą. Ostatecznie więc dla naturalnych a i n mamy:

(a + n + 1) \cdot {{a + n} \choose a} \equiv 0 \pmod{a + 1}
Góra
Mężczyzna Offline
PostNapisane: 8 paź 2016, o 14:22 
Użytkownik

Posty: 306
Lokalizacja: Warszawa
Aha. Można też zauważyć, że:
(m + 1) \cdot {{m} \choose r}=(r+1)\cdot {{m+1} \choose r+1}
co można udowodnić na kilka sposobów. Moim zdaniem najlepiej przez to, że obie strony mają tę samą interpretację kombinatoryczną(jako wybór spośród (m+1)-murarzy drużyny murarskiej składającej się z (r+1) osób wraz z kierownikiem budowy). Wobec tego:
(m+1) \cdot {{m} \choose r}=(r+1)\cdot {{m+1} \choose r+1}\equiv 0\,(\mathrm{mod}\,r+1)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Podzielność przez 30 - zadanie 3  wdsk13  1
 Podzielność liczby przez 2055.  Rokuto  1
 Wykaż podzielność przez 6...  infeq  2
 Podzielność liczb - zadanie 48  natzdw  22
 Podzielność przez 6 - zadanie 2  monikap7  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl