Matematyka.pl

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

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

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

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

\(\displaystyle{ [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:

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

musi być prawdą. Przekształcamy:

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

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

\(\displaystyle{ [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}}\)

\(\displaystyle{ [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}}\)

\(\displaystyle{ [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 \(\displaystyle{ [a + (n - 1) + 1] \cdot {{a + (n - 1)} \choose a}}\) i przekształcać dalej:

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

\(\displaystyle{ (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 \(\displaystyle{ (a + 1) \cdot {{a + n - 1} \choose a - 1}}\) bo, rzecz jasna, jest podzielny przez \(\displaystyle{ a + 1}\) i od razu przekształcamy dwumiany Newtona:

\(\displaystyle{ 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}}\)

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

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

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

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

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

\(\displaystyle{ {{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:

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

Prawdą musi być:

\(\displaystyle{ (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 \(\displaystyle{ n = 0}\) :

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

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

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

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

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

Aha. Można też zauważyć, że:
\(\displaystyle{ (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 \(\displaystyle{ (m+1)}\)-murarzy drużyny murarskiej składającej się z \(\displaystyle{ (r+1)}\) osób wraz z kierownikiem budowy). Wobec tego:
\(\displaystyle{ (m+1) \cdot {{m} \choose r}=(r+1)\cdot {{m+1} \choose r+1}\equiv 0\,(\mathrm{mod}\,r+1)}\)