Cmr : \[C_n^k \] lẻ với mọi k\[ \in \left\{ {1,2,...,n} \right\}\] khi và chỉ khi n có dạng \[n = 2^m - 1\]
Cmr : \[C_n^k \] lẻ với mọi k\[ \in \left\{ {1,2,...,n} \right\}\] khi và chỉ khi n có dạng \[n = 2^m - 1\]
Theo định lý Kummer, luỹ thừa của $2$ trong $C^k_n$ bằng số lần nhớ trong phép tính $n-k$ trong hệ cơ số $2$
Nếu $n=2^m-1$ thì $n=\overline{11..1}_2$ thì $n-k$ sẽ không có lần nhớ nào nên $C^k_n$ lẻ với mọi $k \leq n$
Nếu $n \neq 2^m-1$ thì trong biểu diễn nhị phân của $n$ có ít nhất một số $0$, vì vậy tồn tại $k \leq n$ để $n-k$ có ít nhất một lần nhớ, suy ra tồn tại $C^k_n$ chẵn
Ta có đpcm
bạn có thể trình bày bằng cách dùng định lí Lucas không . Cảm ơn bạn
Bài viết đã được chỉnh sửa nội dung bởi phamxuanvinh08101997: 16-07-2014 - 19:30
Đã đọc bài thì đừng tiếc gì nút Like
Không ngừng vươn xa
Lời giải. Gỉa sử biểu diễn dưới dạng hệ cơ số $2$ của $k,n$ là $k= \sum_{i=0}^{l}a_{i}2^i,n=\sum_{i=0}^l b_i2^i$ với $a_i,b_i \in \{0;1 \}$. Khi đó theo định lý Lucas thì $$\binom{n}{k} \equiv \prod_{i=0}^{l} \binom{b_i}{a_i} \pmod{2}; \; a_i,b_i \in \{0;1 \}.$$
Nếu tồn tại $0 \le j \le l$ thỏa mãn $b_j<a_j$ thì $\binom{n}{k}$ là số chẵn. Do đó $\binom{n}{k}$ lẻ khi và chỉ khi $b_i \ge a_i$ với mọi $0 \le i \le l$, đồng nghĩa với việc $b_i=1$ với mọi $1 \le i \le l$. Khi đó $n=2^{l+1}-1=2^m-1$. $\blacksquare$
Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 17-07-2014 - 07:04
Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.
Grothendieck, Récoltes et Semailles (“Crops and Seeds”).
0 thành viên, 0 khách, 0 thành viên ẩn danh