Bài 23: (Sưu tầm)
Cho $n$ là một số nguyên dương. Gọi $a_n$ là số các số tự nhiên $k$ sao cho $\binom{n}{k}\equiv 1 \pmod{3}$ và $b_n$ là số các số tự nhiên $k$ sao cho $\binom{n}{k}\equiv 2 \pmod{3}$.
Chứng minh rằng: $a_n-b_n$ là một luỹ thừa của 2.
Lời giải. Ta biểu diễn $n$ và $k$ dưới dạng hệ cơ số $3$ như sau $$\begin{array}{l} n=x_m3^m+x_{m-1}3^{m-1}+ \cdots + x_1\cdot 3+x_0, \; x_j \in \{0,1,2 \} \\ k=y_m3^m+y_{m-1}3^{m-1}+ \cdots + y_1 \cdot 3+y_0, \; y_j \in \{ 0,1,2 \}. \end{array}$$
Áp dụng định lý Lucas ta có $$\binom{n}{k} \equiv 1 \pmod{3} \Leftrightarrow \prod_{j=0}^m \binom{x_j}{y_j} \equiv 1 \pmod{3}. \qquad (1)$$
Ta sẽ đi tìm số $k \le n$ thỏa mãn $\binom{n}{k} \equiv 1 \pmod{3}$. Để ý rằng mỗi bộ $m+1$ số $(y_0,y_1, \cdots y_m)$ sẽ cho ta một số $k$ khác nhau, do đó ta sẽ đi đếm bộ $(y_0,y_1, \cdots , y_m)$ thỏa mãn $\prod_{j=0}^m \binom{x_j}{y_j} \equiv 1 \pmod{3}$. Hiển nhiên rằng $x_j \ge y_j \; \forall j=\overline{0,m}$ vì nếu tồn tại $x_k<y_k$ thì $\binom{x_k}{y_k}=0$, không thể thỏa mãn điều kiện $(1)$.
Nếu $x_j=0$ thì $y_j=0$.
Nếu $x_j=1$ thì $y_j=0$ hoặc $y_j=1$.
Nếu $x_j=2$ thì $y_j=0$ hoặc $y_j=1$ hoặc $y_j=2$.
Ta thấy trường hợp $x_j=2,y_j=1$ thì $\binom{2}{1}=2$ còn tất cả các trường hợp còn lại đều cho $\binom{x_j}{y_j}=1$. Do đó để thỏa mãn $(1)$ thì phải có chẵn số bộ $(x_j,y_j)=(2,1)$. Ta đếm như sau:
Gỉa sử $n$ có $l_1$ số $x_j=0$, $l_2$ số $x_j=1$, $l_3$ số $x_j=2$. ($l_1+l_2+l_2=m+1$).
Có $l_1$ số $x_j=0$ nên sẽ có $1$ cách chọn cho $l_1$ số $y_j$ tương ứng (đều bằng $0$). Có $l_2$ số $x_j=1$ nên sẽ có $2^{l_2}$ cách chọn số $y_j$ tương ứng (bằng $0$ hoặc $1$).
Có $l_3$ số $x_j=2$ nên số cách chọn $y_j$ tương ứng sẽ là $\sum_{i=0}^{ \left \lfloor l_3/2 \right \rfloor} \binom{l_3}{2i}2^{l_3-2i}$.
Như vậy có $2^{l_2}\sum_{i=0}^{ \left \lfloor l_3/2 \right \rfloor} \binom{l_3}{2i}2^{l_3-2i}$ cách chọn ra số $k \le n$ thỏa mãn $\binom nk \equiv 1 \pmod{3}$, hay nói cách khác $a_n= 2^{l_2} \sum_{i=0}^{ \left \lfloor l_3/2 \right \rfloor} \binom{l_3}{2i}2^{l_3-2i}$.
Hoàn toàn tương tự, ta cũng tính được $b_n=2^{l_2} \sum_{i=0}^{ \left \lfloor l_3/2 \right \rfloor} \binom{l_3}{2i+1}2^{l_3-2i-1}$. Do đó $$a_n-b_n= 2^{l_2} \left( \sum_{i=0}^{ \left \lfloor l_3/2 \right \rfloor} \binom{l_3}{2i}2^{l_3-2i} - \sum_{i=0}^{ \left \lfloor l_3/2 \right \rfloor} \binom{l_3}{2i+1}2^{l_3-2i-1} \right)=2^{l_2} \cdot (2-1)^{l_3}= \boxed{2^{l_2}}.$$
Bài toán được chứng minh. $\blacksquare$