XLI OM - III etap

III etap XLI Olimpiady Matematycznej

XLI OM - III - Zadanie 1

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

III

Wyznaczyć wszystkie takie funkcje $f: \mathbb{R} \to \mathbb{R}$ , że dla dowolnych liczb rzeczywistych $x$ , $y$ spełniona jest równość

$ (x-y)f(x+y)-(x+y)f(x-y) = 4xy(x^2-y^2) $

Rozwiązanie

Zakładamy, że funkcja $f$ spełnia podane równanie funkcyjne. Wprowadzamy nowe zmienne:

$ (1) \qquad u = x + y, \quad v = x-y. $

Równanie przybiera postać

$ (2) \qquad vf(u)-uf(v) = uv(u^2-v^2). $

(Istotnie: $uv = x^2 - y^2$ ; $u^2 - v^2 = 4xy$ .)

Dla każdej pary liczb rzeczywistych $(u,v)$ istnieje para liczb rzeczywistych $(x,y)$ spełniająca układ równań (1). Zatem jeśli dane w zadaniu równanie jest (dla danej funkcji $f$ ) spełnione przez każdą parę liczb rzeczywistych $(x,y)$ , to równanie (2) jest również spełnione przez każdą parę liczb rzeczywistych $(u,v)$ .

Podstawiając w (2) $u = 1$ , $v = 0$ stwierdzamy, że $f(0) = 0$ .

Niech teraz $u$ , $v$ będą dowolnymi liczbami rzeczywistymi, różnymi od zera. Dzielimy równanie (2) stronami przez $uv$ :

$ (3) \qquad \frac{f(u)}{u} - \frac{f(v)}{v} = u^2-v^2. $

Weźmy pod uwagę funkcję

$ (4) \qquad g(f) = \frac{f(t)}{t} - t^2 \quad \textrm{dla} \ t \ne 0. $

Otrzymany związek (3) odczytujemy jako równość

$ g(u) = g(v) \ \textrm{dla dowolnych} \ u,v \ne 0. $

Innymi słowy, funkcja $g$ jest stała na zbiorze $\mathbb{R}\ {0}$ . Oznaczmy jej stałą wartość przez $c$ . Mamy wówczas, zgodnie z (4),

$ (5) \qquad f(t) = t^3 + ct $

dla $t \ne 0$ . Wcześniej stwierdziliśmy, że $f(0) = 0$ . Tak więc związek (5) jest aluszny dla wszystkich $t \in \mathbb{R}$ .

Nietrudno sprawdzić, że każda funkcja postaci (5) spełnia tożsamościowe związek (2), a więc także i dane w zadaniu równanie funkcyjne. Zatem wzór (5) określa ogólną postać poszukiwanych funkcji.

XLI OM - III - Zadanie 2

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

III

Udowodnić, że jeżeli $n$ jest liczbą naturalną większą od 2, a $x_1, x_2, \ldots , x_n$ są liczbami rzeczywistymi dodatnimi, to

$ \frac{x_1^2}{x_1^2+x_2 x_3} + \frac{x_2^2}{x_2^2+x_3 x_4} + \ldots + \frac{x_n^2}{x_n^2+x_1 x_2} \leq n-1. $

Rozwiązanie

Przyjmijmy

$ a_k = \frac{x_k^2}{x_{k+1}x_{k+2}} \ \textrm{dla} \ k=1,2,\ldots,n; $

stosujemy numerację cykliczną $\bmod{n}$ ; to znaczy, przyjmujemy $x_{n+1} = x_1$ $x_{n+2} = x_2$ . Zauważmy, że

$ (1) \qquad a_1 a_2 \ldots a_n = 1. $

Oznaczmy przez $X$ wyrażenie po lewej stronie danej do udowodnienia nierówności. Przekształcamy:

$ \begin{split} X & = \sum_{k=1}^n \frac{x_k^2}{x_k^2 + x_{k+1}x_{k+2}} = \sum_{k=1}^n \frac{a_k}{a_k+1} = \\ & = \sum_{k=1}^n \left( 1-\frac{1}{a_k+1} \right) = n - \sum_{k=1}^n \frac{1}{a_k+1}. \end{split} $

Aby dowieść, że $X \leq n- 1$ , wystarczy więc pokazać, że

$ (2) \qquad \sum_{k=1}^n \frac{1}{a_k+1} \geq 1. $

Dysponujemy warunkiem (1). Udowodnimy przez indukcję, że dla dowolnej liczby naturalnej $n \geq 2$ oraz dla dowolnych liczb dodatnich $a_1,a_2,\ldots,a_n$ spełniających równość (1) zachodzi nierówność (2).

Gdy $n = 2$ , mamy dwie liczby $a_1$ i $a_2$ , ich iloczyn $a_1a_2 = 1$ . Lewa strona
(2) równa się

$ \frac{1}{a_1+1} + \frac{1}{a_2+1} = \frac{a_1+a_2+2}{(a_1+1)(a_2+1)}= \frac{a_1a_2+a_1+a_2+1}{(a_1+1)(a_2+1)} = 1, $

więc nierówność (2) zachodzi (i staje się równością).

Ustalmy $n \geq 2$ i załóżmy, że dla tej liczby naturalnej $n$ równość (1) implikuje nierówność (2). Chcemy udowodnić analogiczną implikację dla $n + 1$ . Niech więc dane będzie $n+1$ liczb dodatnich $a_1,a_2, \ldots, a_n, a_{n+1}$ , których iloczyn równa się $1$ :

$ a_1 a_2 \ldots a_n a_{n+1} = 1. $

Mamy wykazać, że

$ (3) \qquad \sum_{k=1}^{n+1} \frac{1}{a_k+1} \geq 1. $

Spójrzmy na układ $n$ liczb dodatnich

$ a_1, a_2, \ldots, a_{n-1}, (a_n a_{n+1}). $

Ich iloczyn równa się $1$ , a więc na mocy założenia indukcyjnego zachodzi nierówność (2) z wyrazem $a_n$ zastąpionym przez $a_n a_{n+1}$ :

$ \sum_{k=1}^{n-1} \frac{1}{a_k+1} + \frac{1}{a_n a_{n+1}+1} \geq 1. $

Aby stąd uzyskać tezę indukcyjną (3), wystarczy pokazać, że

$ (4) \qquad \frac{1}{a_n+1} + \frac{1}{a_{n+1}+1} \geq \frac{1}{a_na_{n+1}+1}. $

Pisząc $a$ , $b$ zamiast $a_n$ , $a_{n+1}$ przekształcamy różnicę między lewą i prawą stroną (4), jak następuje:

$ \begin{split} \frac{1}{a+1} + \frac{1}{b+1} + \frac{1}{c+1} & = \frac{(a+b+2)(ab+1) - (a+1)(b+1)}{(a+1)(b+1)(ab+1)} =\\ & = \frac{ab(a+b+1)+1}{(a+1)(b+1)(ab+1)} > 0. \end{split} $

To dowodzi słuszności nierówności (4), a tym samym i (3). Stąd, na mocy zasady indukcji, implikacja (1) $\Longrightarrow$ (2) zachodzi dla dowolnej liczby naturalnej $n\geq 2$ .

W myśl uwag poprzedzających (2) kończy to dowód tezy zadania.

XLI OM - III - Zadanie 3

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

III

W pewnym turnieju uczestniczyło $n$ zawodników. Każdy z nich rozegrał jedną partię z każdym innym zawodnikiem, nie było remisów. Dowieść, że albo można podzielić uczestników turnieju na takie dwie grupy $A$ i $B$ , że każdy zawodnik z grupy $A$ wygrał z każdym z grupy $B$ , albo można ustawić uczestników w ciąg $u_1, u_2, \ldots , u_n$ tak, że $u_1$ wygrał z $u_2$ , $u_2$ wygrał z $u_3$ , ..., $u_{n-1}$ wygrał z $u_n$ , $u_n$ wygrał z $u_1$ .

Rozwiązanie

Stwierdzenie, że zawodnik $x$ był zwycięzcą w spotkaniu z $y$ , będziemy notować za pomocą strzałki: $x \to y$ .

Dowolny ciąg $k$ zawodników $u_1, u_2,\ldots,u_k$ ( $k \geq 3$ ) taki, że

$ u_1 \to u_2 \to u_3 \to \ldots \to u_{k-1} \to u_k \to u_1 $

będziemy nazywać cyklem długości $k$ .

Jeśli $A$ , $B$ są rozłącznymi niepustymi podzbiorami zbioru zawodników, mającymi tę własność, że każdy zawodnik ze zbioru $A$ pokonał każdego zawodnika ze zbioru $B$ , będziemy mówić, że grupa $A$ zdominowała grupę $B$ .

Należy wykazać, że albo zbiór wszystkich zawodników można podzielić na dwa niepuste podzbiory, z których jeden dominuje drugi, albo istnieje cykl długości $n$ .

Rozpatrzymy dwa przypadki.

Przypadek I. Nie istnieje ani jeden cykl.

Weźmy pod uwagą zawodnika $w$ , który wygrał najwięcej partii. Jeśli maksymalna liczba zwycięstw jest udziałem kilku zawodników, wybieramy któregokolwiek z nich (i jego oznaczamy literą $w$ ); zresztą okaże się za chwilę, że taka sytuacja nie jest możliwa - udowodnimy bowiem, że $w$ wygrał wszystkie partie.

Przypuśćmy, że tak nie jest i niech $U$ będzie zbiorem tych zawodników, z którymi $w$ wygrał, zaś $V$ - zbiorem tych zawodników, z którymi $w$ przegrał. W myśl uczynionego przypuszczenia, zbiór $V$ nie jest pusty. Wybierzmy dowolnego zawodnika $v$ ze zbioru $V$ . Gdyby się okazało, że $v$ pokonał wszystkich zawodników ze zbioru $U$ , znaczyłoby to, że $v$ ma na swym koncie więcej zwycięstw niż $w$ , co nie jest możliwe. Musi więc istnieć w zbiorze $U$ zawodnik $u$ , który wygrał z $v$ . Trójka zawodników $u$ , $v$ , $w$ tworzy cykl: $u \to v \to w \to u$ , wbrew założeniu o nieistnieniu cykli. Otrzymana sprzeczność dowodzi niesłuszności przypuszczenia otwierającego ten akapit.

Wykazaliśmy w ten sposób, że zawodnik w pokonał wszystkich innych. Wystarczy teraz określić grupę $A$ jako zbiór jednoelementowy, zaliczając doń zawodnika $w$ ; wszyscy pozostali zawodnicy utworzą grupę $B$ , która jest zdominowana przez $A$ . Twierdzenie jest więc udowodnione w tym przypadku.

(Zauważmy, że wskazana metoda podziału nie jest jedyna; na przykład, można by było określić $B$ jako zbiór jednoelementowy, zaliczając doń tego zawodnika, który poniósł najwięcej porażek, a pozostałych zawodników umieszczając w grupie $A$ ; dowód poprawności i skuteczności takiego podziału byłby w pełni analogiczny. Zachęcamy Czytelników do znalezienia jeszcze innych metod dobrego podziału.)

Przypadek II. Istnieje co najmniej jeden cykl.

Niech $m$ będzie największą liczbą naturalną taką, że istnieje cykl długości $m$ . Jeżeli $m = n$ , znaczy to, że wszystkich zawodników można ustawić w cykl, więc zachodzi teza zadania.

W dalszym ciągu przyjmijmy, że $m < n$ . Niech

$ w_1 \to w_2 \to \ldots \to w_{m-1} \to w_m \to w_1 $

będzie cyklem długości $m$ i niech $z$ będzie dowolnym zawodnikiem różnym od $w_1$ , $w_2$ , \ldots, $w_m$ . Wykażemy, że wszyscy zawodnicy $w_i$ uzyskali w meczu z zawodnikiem $z$ identyczny rezultat (wszyscy wygrali albo wszyscy przegrali).

Przypuśćmy, że jest inaczej. Można wówczas wskazać dwóch kolejnych (w sensie cyklicznej numeracji) zawodników $w_j$ , $w_{j+1}$ , z których pierwszy wygrał z zawodnikiem $z$ , a drugi przegrał. Umieszczając $z$ między $w_j$ a $w_{j+1}$ tworzymy nowy cykl

$ w_1 \to \ldots \to w_j \to z \to w_{j+1} \to w_m \to w_1, $

długości $m+1$ . Jest to sprzeczność z maksymalnością liczby $m$ jako długości.

Zatem istotnie każdy zawodnik spoza maksymalnego cyklu albo wygrał albo przegrał wszystkie mecze z zawodnikami należącymi do tego cyklu. Możemy w takim razie podzielić wszystkich zawodników różnych od $w_1, \ldots, w_m$ na dwa podzbiory $U$ , $V$ , zaliczając do $U$ tych, którzy przegrali spotkania z wszystkimi $w_i$ , a do $V$ - tych, którzy wszystkie spotkania z zawodnikami $w_i$ wygrali. Może się zdarzyć, że jeden ze zbiorów $U$ , $V$ będzie pusty - nie mogą jednak oba być puste; wynika to z założenia, że $m < n$ .

Jeśli zbiór $U$ jest pusty, to przyjmując

$ A = V, \quad B = \{w_1,\ldots,w_m\} $

mamy podział zbioru wszystkich zawodników na grupy $A$ , $B$ takie, że $A$ dominuje $B$ . Jeżeli zbiór $V$ jest pusty, żądany podział uzyskamy biorąc

$ A = \{w_1,\ldots,w_m\}, \quad B = U. $

Przyjmijmy więc, że zbiory $U$ , $V$ są oba niepuste. Niech $u$ będzie dowolnym zawodnikiem ze zbioru $U$ , a $v$ - dowolnym zawodnikiem ze zbioru $V$ . Przypuśćmy, że $u$ wygrał z $v$ . W myśl określenia zbiorów $U$ i $V$ , zawodnik $u$ przegrał, a zawodnik $v$ wygrał mecze z wszystkimi $w_i$ ; w szczególności $u$ przegrał z $w_m$ , natomiast $v$ wygrał z $w_1$ . Mamy wobec tego cykl

$ u \to v \to w_1 \to w_2 \to \ldots \to w_{m-1} \to w_m \to u, $

długości $m+2$ ; sprzeczność z maksymalnością $m$ . Zatem zawodnik $u$ nie mógł wygrać z $v$ .

Ponieważ zawodników $u \in U$ , $v \in V$ wybraliśmy dowolnie, dochodzimy do wniosku, że wszyscy zawodnicy ze zbioru $U$ przegrali z wszystkimi zawodnikami ze zbioru $V$ ; zbiór $U$ jest zdominowany przez $V$ .

Wystarczy teraz przyjąć

$ A = V, \quad B = U \cup \{w_1,\ldots,w_m\}, $

lub też

$ A = V \cup \{w_1,\ldots,w_m\}, \quad B = U, $

aby uzyskać podział spełniający zadane warunki: przy każdym z tych dwóch określeń grupa $A$ dominuje $B$ .

Dowód jest zakończony.

XLI OM - III - Zadanie 4

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

III

Wewnątrz kwadratu o boku długości 1 narysowano trójkąt, którego każdy bok ma długość nie mniejszą od 1. Dowieść, że środek kwadratu należy do trójkąta.

Rozwiązanie

Stosujemy dowód nie wprost.

Przypuśćmy, że środek $O$ danego kwadratu $ABCD$ nie należy do narysowanego trójkąta $A$ . Istnieje wówczas prosta $l$ przechodząca przez $O$ i taka, że trójkąt $A$ leży w całości po jednej stronie tej prostej (tzn. zawiera się w jednej z dwóch półpłaszczyzn otwartych wyznaczonych przez prostą $l$ , patrz: Uwaga).

Oznaczmy punkty przecięcia prostej $l$ z brzegiem kwadratu przez $A'$ i $C'$ ; możemy przyjąć (w razie potrzeby przesuwając cyklicznie oznaczenia wierzchołków kwadratu), że punkt $A'$ leży na boku $AB$ , a punkt $C$ - na boku $CD$ , przy czym $A' \ne B$ , $C' \ne D$ .

Poprowadźmy przez punkt $O$ prostą $m$ prostopadłą do $l$ . Przecina ona brzeg kwadratu w punktach $B'$ i $D'$ leżących odpowiednio na bokach $BC$ i $DA$ , przy czym $B' \ne C$ , $D'\ne A$ (rysunek 7).

Proste $l$ i $m$ dzielą kwadrat na cztery przystające figury. Trójkąt $A$ leży po jednej stronie prostej $l$ , a więc zawiera się w sumie dwóch spośród tych figur. Jedna z nich musi zawierać co najmniej dwa wierzchołki trójkąta $A$ , czyli końce odcinka o długości nie mniejszej od $1$ . Niech to będzie część kwadratu wycięta przez półproste $(OA')^\to$ i $(OB')^\to$ (takie założenie nie uszczupla ogólności rozważań).

W szczególnym przypadku, gdy proste $l$ i $m$ zawierają przekątne kwadratu $ABCD$ (tj. gdy $A = A'$ , $B = B'$ , $C = C'$ , $D = D'$ ), rozważana figura jest trójkątem $OAB$ . Jedynym odcinkiem długości $\geq 1$ zawartym w tym trójkącie jest jego przeciwprostokątna $AB$ . Znaczyłoby to, że odcinek $AB$ jest jednym z boków trójkąta $A$ - wbrew założeniu, że trójkąt $A$ leży wewnątrz kwadratu $ABCD$ .

W pozostałym przypadku ( $A \ne A'$ itd.) rozważana figura jest czworokątem $OA'BB'$ , w którym kąty przy wierzchołkach $O$ i $B$ są proste - można więc na nim opisać koło. Jego średnicą jest odcinek $A'B'$ o długości mniejszej od $1$ (bo $A'B'C'D'$ jest kwadratem wpisanym w $ABCD$ , nie identycznym z $ABCD$ ). Wobec tego figura (czworokąt) $OA'BB'$ nie może zawierać pary punktów odległych co najmniej o $1$ - wbrew temu, co stwierdziliśmy chwilę wcześniej.

Otrzymana sprzeczność kończy dowód.

Uwaga. W rozwiązaniu skorzystaliśmy z faktu, że przez dowolny punkt $O$ leżący poza danym trójkątem $\Delta$ można poprowadzić taką prostą $Z$ , że trójkąt $\Delta$ leży w całości po jednej jej strome. Może warto podać ścisłe uzasadnienie tego faktu.

Trójkąt jest częścią wspólną trzech półpłaszczyzn domkniętych, których krawędziami są proste zawierające jego boki. Skoro punkt $O$ nie należy do danego trójkąta, to nie należy do co najmniej jednej z tych półpłaszczyzn. Niech $l'$ będzie jej krawędzią (jeśli są dwie takie półpłaszczyzny, wybieramy jedną z nich, i jej krawędź oznaczamy przez $l'$ ). Prosta $Z$ , równoległa do $V$ i przechodząca przez $O$ , ma żądaną własność.

XLI OM - III - Zadanie 5

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

III

Dany jest taki ciąg liczb naturalnych $(a_n)$ , że $\lim_{n\to \infty} \frac{n}{a_n} = 0$ .

Udowodnić, że istnieje taka liczba $k$ , dla której między liczbami $a_1 + a_2 + \ldots + a_k$ oraz $a_1 + a_2 + \ldots + a_k + a_{k+1}$ znajduje się co najmniej 1990 kwadratów liczb naturalnych.

Rozwiązanie

Oznaczmy:

$ s_n = a1+a_2 + ldots + a_n, \quad r_n = \sqrt{s_{n+1}} - \sqrt{s_n} > 0. $

Oszacujemy z dołu wyrazy ciągu ( $r_n$ ). Dla $n > i$ mamy

$ \begin{split} (1) \qquad r_{n-1} = \sqrt{s_n} - \sqrt{s_{n-1}} & = \frac{s_n - s_{n-1}}{\sqrt{s_n} + \sqrt{s_{n-1}}} = \\ & = \frac{a_n}{\sqrt{s_n} + \sqrt{s_{n-1}}} > \frac{a_n}{2\sqrt{s_n}}. \end{split} $

Z założenia zadania wynika, że ciąg ( $a_n/n$ ) dąży do nieskończoności; tym bardziej i sam ciąg ( $a_n$ ) dąży do nieskończoności. Zatem dla nieskończenie wielu $n$ zachodzi nierówność

$ (2) \qquad a_n \geq \max \{a_1,a_2,\ldots,a_n\}. $

Niech $n$ będzie jednym z tych wskaźników, dla których (2) zachodzi. Mamy wówczas, zgodnie z (1),

$ \left( \frac{1}{2r_{n-1}} \right)^2 < \frac{s_n}{a_n^2} = \frac{1}{a_n} \sum_{k=1}^n \frac{a_k}{a_n} \leq \frac{1}{a_n} \sum_{k=1}^n 1 = \frac{n}{a_n}. $

Nierówność ta zachodzi dla nieskończenie wielu $n$ . Ponieważ zaś ciąg ( $n/a_n$ ) dąży do zera, dostajemy wniosek, że pewien podciąg ciągu ( $r_n$ ) dąży do nieskończoności.

Istnieje wobec tego taki numer $k$ , że $r_k> 1990$ . Znaczy to, że długość przedziału $(\sqrt{s_k};\sqrt{s_{k+1}})$ przekracza $1990$ . W takim przedziale można znaleźć $1990$ liczb naturalnych. Ich kwadraty leżą w przedziale $(s_k;s_{k+1})$ . Znalezienie przedziału tej postaci i o tej własności było właśnie treścią zadania.

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).