XLI OM - III - Zadanie 6

Udowodnić, że dla każdej liczby naturalnej $ n $ większej od 2 liczba

\[<br />
\sum_{k=0}^{[n/3]} \binom{n}{3k}<br />
\]

jest podzielna przez 3.

Rozwiązanie

Podstawą wszelkich operacji na współczynnikach dwumianowych jest tożsamość

\[<br />
(1) \qquad \binom{n+1}{j} = \binom{n}{j} + \binom{n}{j-1}.<br />
\]

Wygodnie jest rozszerzyć zakres definicji symbolu $ \binom{n}{j} $ na dowolne całkowite wartości $ j $, przyjmując

\[<br />
\binom{n}{j}=0 \quad \textrm{dla} \ j < 0 \ \textrm{oraz dla} \ j > n<br />
\]

($ n $ jest nadal liczbą całkowitą nieujemną). Przy takiej umowie wzór (1) obowiązuje bez żadnych ograniczeń na $ j $; w szczególności również jedynki w trójkącie Pascala powstają zgodnie z regułą (1). Innymi słowy: traktujemy wiersze trójkąta Pascala jako ciągi obustronnie nieskończone, wypełnione zerami na lewo i na prawo od skrajnych jedynek; wyrazy każdego z tych ciągów są ponumerowane liczbami całkowitymi (także ujemnymi). Wyrazy o numerach ujemnych są zerami; lewa jedynka jest wyrazem o numerze $ 0 $, prawa jedynka jest wyrazem o numerze równym numerowi wiersza; dalsze wyrazy znów są zerami. Każda liczba w wierszu $ n $-tym jest sumą liczb znajdujących się nad nią w wierszu ($ n - 1 $)-ym, i to właśnie orzeka podstawowa równość (1).

Będziemy rozważać sumy

\[<br />
A_k = \sum_k (-1)^k \binom{n}{3k}, \ B_n = \sum_k (-1)^k \binom{n}{3k-1},\ C_n = \sum_k (-1)^k \binom{n}{3k-2}.<br />
\]

Nie piszemy zakresu zmienności wskaźnika sumowania; można przez to rozumieć, że $ k $ przebiega wszystkie wartości całkowite - nie powoduje to niejasności, bowiem składniki tych sum są różne od zera tylko dla skończenie wielu wartości $ k $. I tak, na przykład, w wyrażeniu $ A_n $ niezerowe składniki otrzymujemy tylko dla $ k $ od $ 0 $ do $ [n/3] $. Zatem $ A_n $ jest tym wyrażeniem, którego dotyczy zadanie.

Udowodnimy przez indukcję, że

\[<br />
(2) \qquad A_n \equiv B_n \equiv C_n \equiv 0   \bmod{3} \quad \textrm{dla}\ n \geq 3.<br />
\]

(W zadaniu żąda się jedynie dowodu tego, że $ A_n \equiv 0 \bmod{3} $); rozbudowanie tezy do postaci (2) jest jednak celowe, aby dało się wykonać krok indukcyjny - por. Uwaga 1 w rozwiązaniu zadania 7 z zawodów pierwszego stopnia.)

Dla $ n = 3 $: trzeci wiersz trójkąta Pascala ma postać $ \ldots 001331000 \ldots $ (jedynki na miejscach o numerach $ 0 $ i $ 3 $). Tak więc $ A_3 = 1 - 1 = 0 $, $ B_3 = -3 $, $ C_3 = -3 $; zależności (2) zachodzą.

Ustalmy liczbę naturalną $ n \geq 3 $ i załóżmy indukcyjnie, że

\[<br />
A_n \equiv B_n \equiv C_n \equiv O \bmod{3}.<br />
\]

Zgodnie z wzorem (1) mamy

\[<br />
\begin{split}<br />
A_{n+1} & = \sum_k (-1)^k \binom{n+1}{3k} =\\<br />
& = \sum_k (-1)^k \binom{n}{3k} + \sum_k (-1)^k \binom{n}{3k-1} = A_n + B_n,\\<br />
B_{n+1} & = \sum_k (-1)^k \binom{n+1}{3k-1} =\\<br />
& = \sum_k (-1)^k \binom{n}{3k-1} + \sum_k (-1)^k \binom{n}{3k-2} = B_n + C_n,\\<br />
C_{n+1} & = \sum_k (-1)^k \binom{n+1}{3k-2} =\\<br />
& = \sum_k (-1)^k \binom{n}{3k-2} + \sum_k (-1)^k \binom{n}{3k-3} =\\<br />
& = \sum_k (-1)^k \binom{n}{3k-2} + \sum_l (-1)^{l+i} \binom{n}{3l} = \\<br />
& = \sum_k (-1)^k \binom{n}{3k-2} - \sum_l (-1)^l \binom{n}{3l} = C_n - A_n.<br />
\end{split}<br />
\]

Z otrzymanych wzorów rekurencyjnych wynika oczywiście, że

\[<br />
A_{n+1} \equiv B_{n+1} \equiv C_{n+1} \equiv 0 \bmod{3}.<br />
\]

Na mocy zasady indukcji dowodzi to słuszności tezy (2).

Komentarze

Dodaj nową odpowiedź