Chủ đề này có 1 trả lời

[zipienie]

Với $n\in \mathbb{N} $, ta xét các tập hợp: $A= \{k|C_n^{k}\equiv 1\pmod 3 \},B= \{k|C_n^{k}\equiv 2 \pmod 3 \}.$ Đặt $ a_n=|A|,b_n=|B| $.
Chứng minh rằng $a_n-b_n$ là một lũy thừa của $2$.
 

Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 31-08-2014 - 23:07

[Zaraki]

Với $n\in \mathbb{N} $, ta xét các tập hợp: $A= \{k|C_n^{k}\equiv 1\pmod 3 \},B= \{k|C_n^{k}\equiv 2 \pmod 3 \}.$ Đặt $ a_n=|A|,b_n=|B| $.
Chứng minh rằng $a_n-b_n$ là một lũy 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$