XLI OM - III - Zadanie 6

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

III

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

$ \sum_{k=0}^{[n/3]} \binom{n}{3k} $

jest podzielna przez 3.

Rozwiązanie

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

$ (1) \qquad \binom{n+1}{j} = \binom{n}{j} + \binom{n}{j-1}. $

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

$ \binom{n}{j}=0 \quad \textrm{dla} \ j < 0 \ \textrm{oraz dla} \ j > n $

( $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

$ 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}. $

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

$ (2) \qquad A_n \equiv B_n \equiv C_n \equiv 0 \bmod{3} \quad \textrm{dla}\ n \geq 3. $

(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

$ A_n \equiv B_n \equiv C_n \equiv O \bmod{3}. $

Zgodnie z wzorem (1) mamy

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

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

$ A_{n+1} \equiv B_{n+1} \equiv C_{n+1} \equiv 0 \bmod{3}. $

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