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

[QUANVU]

Chứng minh rằng:
$$\sum\limits_{k=0}^{n}(-1)^kC_n^k(x-k)^n=n!, \forall x\in \mathbb{R}.$$

[perfectstrong]

Bài này mình nghĩ phải là
\[
\sum\limits_{k = 0}^n {\left( { - 1} \right)^k C_n^k \left( {n - k} \right)^n } = n! \quad \forall n \in \mathbb{N}^*
\]
Nếu thế thì lời giải như sau:
Lời giải:
Trước hết, ta cần 2 bổ đề sau:
Bổ đề 1: Số toàn ánh từ tập $A$ có $m$ phần tử vào tập $B$ có $n$ phần tử (với $m \ge n$) là
\[
\sum\limits_{k = 0}^n {\left( { - 1} \right)^k C_n^k \left( {n - k} \right)^m } \quad (1)
\]
Chứng minh:
Xét $A=\lbrace x_1;x_2;...;x_m \rbrace;\, B=\lbrace y_1;y_2;...;y_n \rbrace$
Gọi $F$ là tập tất cả các ánh xạ $f:A \to B$.
Cứ mỗi phần tử $x_i \in A$, sẽ có $n$ cách chọn phần tử $y_j \in B$ sao cho $f(x_i)=y_j$.
Do đó $|F|=n^m$ vì $A$ có $m$ phần tử.
Đặt $C_i \, (i=\overline{1,n})$ là tập tất cả các ánh xạ $f:A \to B$ sao cho $f(x) \ne y_i \, \, \forall x \in A$.
Do cách đặt nên $C_i \subset F\, \forall i=\overline{1,n}$.
Gọi $D$ là tập tất cả các toàn ánh $f:A \to B$. Suy ra $D \cap C_i=\emptyset , \forall i=\overline{1,n}$.
Mà ta có \[
F = D \cup \bigcup\limits_{i = 1}^n {C_i } \Rightarrow \left| F \right| = \left| D \right| + \left| {\bigcup\limits_{i = 1}^n {C_i } } \right| \quad (2)
\]
Lại có:
\[
\left| {\bigcup\limits_{i = 1}^n {C_i } } \right| = \sum\limits_{i = 1}^n {\left| {C_i } \right|} - \sum\limits_{1 \le i < j \le n}^{} {\left| {C_i \cap C_j } \right|} + \sum\limits_{1 \le i < j < k \le n}^{} {\left| {C_i \cap C_j \cap C_k } \right|} - ... + \left( { - 1} \right)^{n + 1} \left| {\bigcap\limits_{i = 1}^n {C_i } } \right|
\]
Xét $|C_i|$. Cứ ứng với một phần tử $x \in A$, sẽ có $n-1$ cách chọn phần tử $y \in B$ (vì $y \ne y_i$) sao cho $f(x_t)=y_z$.
Do đó $|C_i|=(n-1)^m$ vì $A$ có $m$ phần tử.
Mà có $C_n^1$ tập $C_i$ nên $$\sum\limits_{i = 1}^n {\left| {C_i } \right|} = C_n^1 \left( {n - 1} \right)^m$$
Tương tự, xét $\left| {C_{i_1 } \cap C_{i_2 } \cap ... \cap C_{i_k } } \right|$.
Cứ ứng với một phần tử $x \in A$, sẽ có $n-k$ cách chọn phần tử $y \in B$ (vì $y \ne y_{i_j} \, \forall j=\overline{1,k}$) sao cho $f(x)=y$.
Do đó $\left| {C_{i_1 } \cap C_{i_2 } \cap ... \cap C_{i_k } } \right|=(n-k)^m$ vì $A$ có $m$ phần tử.
Mà có $C_n^k$ tập dạng $C_{i_1 } \cap C_{i_2 } \cap ... \cap C_{i_k }$ nên \[
\sum\limits_{1 \le i_1 < i_2 < ... < i_k \le n}^{} {\left| {C_{i_1 } \cap C_{i_2 } \cap ... \cap C_{i_k } } \right|} = C_n^k \left( {n - k} \right)^m
\]
Do đó
\[
\begin{array}{l}
\left| {\bigcup\limits_{i = 1}^n {C_i } } \right| = C_n^1 \left( {n - 1} \right)^m - C_n^2 \left( {n - 2} \right)^m + C_n^3 \left( {n - 3} \right)^m - ... + \left( { - 1} \right)^{n + 1} C_n^n 0^m \\
\left( 2 \right) \Rightarrow \left| D \right| = \left| F \right| - \left| {\bigcup\limits_{i = 1}^n {C_i } } \right| = n^m - C_n^1 \left( {n - 1} \right)^m + C_n^2 \left( {n - 2} \right)^m - ... + \left( { - 1} \right)^n C_n^n 0^m \\
\Rightarrow \left| D \right| = \sum\limits_{k = 0}^n {\left( { - 1} \right)^k C_n^k \left( {n - k} \right)^m } \\
\end{array}
\]
Vậy (1) được chứng minh.
========================================
Bổ đề 2: Số song ánh từ tập $A$ có $n$ phần tử vào tập $B$ có $n$ phần tử là $n!$.
Chứng minh:
Xét $A=\lbrace x_1;x_2;...;x_m \rbrace;\, B=\lbrace y_1;y_2;...;y_n \rbrace$
Gọi $f$ là song ánh đi từ $A$ vào $B$.
Có $n$ cách chọn $y_k \in B$ sao cho $f(x_1)=y_k$.
Có $n-1$ cách chọn $y_t \in B$ sao cho $f(x_2)=y_t$, vì $f$ là song ánh nên $x_1 \ne x_2 \Rightarrow f(x_1) \ne f(x_2)$.
....
Có $1$ cách chọn $y \in B$ sao cho $f(x_n)=y$.
Như vậy, số song ánh $f: A \to B$ là $n(n-1)(n-2)...1=n!$. Bổ đề 2 được chứng minh.
========================================
Quay lại bài toán.
Xét 2 tập $A$ có $n$ phần tử và tập $B$ có $n$ phần tử.
Theo bổ đề 2 thì số song ánh $f:A \to B$ là $n!$.
Mặt khác, nếu toàn ánh $g: A\to B$ thì $g$ cũng là song ánh, vì $|A|=|B|$.
Do đó, theo bổ đề 1, số song ánh $f:A\to B$ là $\sum\limits_{k = 0}^n {\left( { - 1} \right)^k C_n^k \left( {n - k} \right)^n }$.
Suy ra
\[
\sum\limits_{k = 0}^n {\left( { - 1} \right)^k C_n^k \left( {n - k} \right)^n } = n! \quad \forall n \in \mathbb{N}^*
\]
Bài toán được chứng minh.
========================================
========================================
Nếu như đề là
\[
\sum\limits_{k = 0}^n {\left( { - 1} \right)^k C_n^k \left( {x - k} \right)^n } = n! \quad \forall x \in \mathbb{R}
\]
thì khi chọn $x \in \mathbb{N}^*$ sao cho $x>n$ thì theo bổ đề 1, VT chính là số toàn ánh $f$ từ tập có $x$ phần tử vào tập có $n$ phần tử. Nhưng VT chỉ là số song ánh từ tập có $n$ phần tử và tập có $n$ phần tử. Mà dễ dàng chỉ ra rằng tồn tại 1 toàn ánh không là song ánh. Còn mọi song ánh đều là toàn ánh. Nên suy ra $VT>VP$????

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 18-09-2012 - 20:37

[PSW]

Bài này thuộc gameshow Những bài toán trong tuần

Hiện tại, BTC chưa kiểm chứng được lời giải của Hân nên sẽ tạm để vậy và chấm điểm sau. Rất mong các bạn cũng kiểm tra để khẳng định hay phủ định đề bài của bác QUANVU

[hxthanh]

Chứng minh rằng:
$$\sum\limits_{k=0}^{n}(-1)^kC_n^k(x-k)^n=n!, \forall x\in \mathbb{R}.$$

Đề bài hoàn toàn chính xác!
Cách giải quyết như sau:
Xét đa thức: $P(x)=\sum\limits_{k=0}^{n}(-1)^kC_n^k(x-k)^n - n!$
Bước 1: Chỉ ra $P(x)$ là đa thức bậc $<n$ của $x$
Bước 2: Chỉ ra $n$ giá trị phân biệt của $x$ để $P(x)=0$
Kết luận: $P(x) \equiv 0$

Dễ thấy hệ số của $x^n$ trong $(x-k)^n$ bằng $1$
khi đó: $\sum\limits_{k=0}^{n}(-1)^kC_n^k=(1-1)^n=0$
do đó $P(x)$ có bậc chưa tới $n$

Mặt khác ta có:
$P(x)=\sum\limits_{k=0}^{n}(-1)^kC_n^k(x-k)^n - n! = \sum\limits_{k=0}^{n}(-1)^{n-k}C_n^{n-k}(x-(n-k))^n - n!$ (Đảo chiều biến chạy)
$P(x)=\sum\limits_{k=0}^{n}(-1)^{n+k}C_n^k (x-n+k)^n - n!=\sum\limits_{k=0}^{n}(-1)^k C_n^k ((n-x)-k)^n - n!$
$P(x)=P(n-x)\quad(*)$

Mà perfectstrong đã chứng minh (rất chính xác và hay) trường hợp $P(n)=0$
Theo $(*)$, ta có
Thay $x$ bởi $-n$ ta được $P(-n)=P(2n)$ hay $P(n)=P(-2n)=0$ (thay $-n$ bởi $n$)
Lại từ $(*)$ thay $x$ bởi $3n$ ta được $P(3n)=P(-2n)=0$
v.v...
Cứ như vậy ta có thể chỉ ra vô số giá trị để $P(x)=0$, nhưng $P(x)$ lại có bậc hữu hạn, từ đó suy ra $P(x)\equiv 0\;\forall x\in\mathbb R$

...
========================================
Nếu như đề là
\[
\sum\limits_{k = 0}^n {\left( { - 1} \right)^k C_n^k \left( {x - k} \right)^n } = n! \quad \forall x \in \mathbb{R}
\]
thì khi chọn $x \in \mathbb{N}^*$ sao cho $x>n$ thì theo bổ đề 1, VT chính là số toàn ánh $f$ từ tập có $x$ phần tử vào tập có $n$ phần tử. Nhưng VT chỉ là số song ánh từ tập có $n$ phần tử và tập có $n$ phần tử. Mà dễ dàng chỉ ra rằng tồn tại 1 toàn ánh không là song ánh. Còn mọi song ánh đều là toàn ánh. Nên suy ra $VT>VP$????

Ở chỗ này perfectstrong đã hơi vội, nên kết luận nhầm. Theo bổ đề thì số toàn ánh $f$ từ tập có $x$ phần tử vào tập có $n$ phần tử phải là
\[
\sum\limits_{k = 0}^n {\left( { - 1} \right)^k C_n^k \left( {n - k} \right)^x }
\]

[Trungpbc]

Chứng minh rằng:
$$\sum\limits_{k=0}^{n}(-1)^kC_n^k(x-k)^n=n!, \forall x\in \mathbb{R}.$$

Ta sẽ chứng minh khẳng định tổng quát hơn.
Cho đa thức: $$f(X)=a_{n}X^{n}+a_{n-1}X^{n-1}+...+a_{1}X+a_{0}$$ Khi đó với mọi số thực $h$ khác $0$ và mọi số thực $x$, ta có đẳng thức $$\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}f(x+kh)=a_{n}.n!.h^{n}$$ Lời giải
Áp dụng công thức nội suy lagrange cho $f$ tại $n+1$ nút nội suy $x+kh,k=0,1,...,n$ ta có $$f(X)=\sum_{k=0}^{n}f(x+kh)\prod _{i\neq k}\frac{X-(x+ih)}{(x+kh)-(x+ih)}=\sum_{k=0}^{n}f(x+kh)\prod _{i\neq k}\frac{X-(x+ih)}{h(k-i)}$$ Đồng nhất hệ số của $X^{n}$ hai vế với chú ý $$\prod _{i\neq k}\left [{h(k-i)} \right ]^{-1}=\frac{(-1)^{n-k}}{h^{n}k!(n-k)!}=\frac{(-1)^{n-k}}{h^{n}n!}\binom{n}{k}$$ ta suy ra $$a_{n}=\sum_{k=0}^{n}\frac{(-1)^{n-k}}{h^{n}n!}\binom{n}{k}f(x+kh)$$ Hay tương đương với $$a_{n}.h^{n}n!=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}f(x+kh)$$Tóm lại ta có đpcm, trong bài toán của Quanvu là một hệ quả khi chọn đa thức $f(X)=X^{n}$ và $h=-1$. Qua đây cũng có thể thấy rằng, công thức nội suy Lagrange gần như giải quyết được toàn bộ các đẳng thức tổ hợp mà bằng con đường tổ hợp thuần túy rất khó tiếp cận!

[Trungpbc]

Ta sẽ chứng minh khẳng định tổng quát hơn.
Cho đa thức: $$f(X)=a_{n}X^{n}+a_{n-1}X^{n-1}+...+a_{1}X+a_{0}$$ Khi đó với mọi số thực $h$ khác $0$ và mọi số thực $x$, ta có đẳng thức $$\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}f(x+kh)=a_{n}.n!.h^{n}$$

Đẳng thức trên không hề tầm thường, nó là một trong những bổ đề quan trọng giải quyết những bài đa thức khó. Tiêu biểu trong số đó là bài toán sau:
Bài toán. Cho hai đa thức $P,Q$ cới hệ số nguyên sao cho với mọi số nguyên dương $n$, $P(n), Q(n)$ là những số nguyên dương thỏa mãn $$2^{Q(n)}-1|3^{P(n)}-1$$Chứng minh rằng $Q$ là đa thức hằng.
Lời giải.
Cố định một số nguyên dương $n$, đặt $a=o_{2^{Q(n)-1}}(3)$ (kí hiệu $o_{p}(x)$ để chỉ bậc của $x$ modulo $p$). Từ giả thiết suy ra $$3^{P(n)}-1\equiv 0\pmod{2^{Q(n)}-1}$$ Suy ra $a|P(n)$. Mặt khác với mọi số nguyên dương $k$ thì ta có $Q(n+kQ(n))\equiv 0\pmod{Q(n)}$. Do đó, kết hợp với giả thiết cho ta $$3^{P(n+kQ(n))}\equiv 1\pmod{2^{Q(n)}-1}$$ Suy ra $$P(n+kQ(n))\equiv 0\pmod a,\forall k\in \mathbb{N}$$ Từ đó, chọn $m=\deg P$, ta có $$a|\sum_{k=0}^{m}(-1)^{m-k}\binom{m}{k}P(n+kQ(n))=p.Q(n)^{m}m!$$ trong đó, $p$ là hệ số bậc cao nhất của $P$. Suy ra, $a|\gcd\left (P(n);p.m!Q(n)^{k} \right )$. Mặt khác, do hai đa thức $P,Q$ nguyên tố cùng nhau nên theo định lí Bezout, tồn tại số nguyên dương $A$ và hai đa thức $S,R$ với hệ số nguyên sao cho $$P(x).S(x)+Q(x).R(x)=A$$ Hệ quả là, $\gcd(P(n),Q(n))|A $ hay $\gcd(P(n),Q(n))$ bị chặn. Và như thế, $\gcd(P(n),p.m!Q(n)^{k})$ bị chặn hay $a=o_{2^{Q(n)}-1}(3)$ bị chặn. Suy ra $2^{Q(n)}-1|3^{a}-1$ bị chặn. Điều này chứng tỏ, $Q$ phải là hằng số.

Bài viết đã được chỉnh sửa nội dung bởi Trungpbc: 10-11-2012 - 08:26

[perfectstrong]

Bài toán trungpbc đưa ra chính là IMO SL 2011. Đây là một lời giải khác được đưa ra.
Official Solution:
Ta sẽ chứng minh rằng tồn tại số nguyên dương $d$ sao cho $gcd(Q(n);P(n)) \le d\quad \forall n$.
Thật vậy, $P,Q$ nguyên tố cùng nhau nên tồn tại đa thức $R_0(x);S_0(x) \in \mathbb{Q}[x]$ sao cho $P(x)R_0(x)-Q(x)S_0(x)=1 \quad \forall x$.
Chọn số nguyên dương $d$ thích hợp sao cho $R(x)=dR_0(x);S(x)=dS_0(x)$ là các đa thức hệ số nguyên.
Khi đó $P(x)R(x)-Q(x)S(x)=d \quad \forall x$. Suy ra $gcd(Q(n);P(n)) \le d \quad \forall n$.
Giả sử rằng $Q(x)$ không là đa thức hằng. Do đó $Q(x)$ không bị chặn. Tồn tại số nguyên dương $m$ sao cho
\begin{equation}
\label{1}
M=2^{Q(m)-1} \ge 3^{\max \lbrace P(1);P(2);...;P(d) \rbrace}
\end{equation}
Từ giả thiết, suy ra $2;3 \not | M$. Gọi $a,b$ thứ tự là cấp của $2;3$ modulo $M$.
Dễ thấy rằng $a=Q(m)$ (vì $M$ không là lũy thừa của $2$) và $3|P(m)$. Do đó $gcd(a;b) \le gcd(P(m);Q(m)) \le d$.
Tích số $ax-by$ nhận mọi giá trị nguyên chia hết cho $gcd(a;b)$ khi $x,y$ quét hết tập số tự nhiên.
Do đó, tồn tại $x,y$ là số tự nhiên sao cho $1 \le m+ax-by \le d$.
Từ $Q(m) \equiv Q(m+ax) \pmod a$ nên
\[ 2^{Q(m)} \equiv 2^{Q(m+ax)} \equiv 1 \pmod M\]
Do đó, theo gt
\[ M|2^{Q(m+ax)}-1|3^{P(m+ax)}-1\]
Lại từ $P(m+ax) \equiv P(m+ax-by) \pmod b$ nên
\[ 3^{P(m+ax-by)} \equiv 3^{P(m+ax)} \equiv 1 \pmod M\]
Vì $P(m+ax-by)>0 \Rightarrow M \le 3^{P(m+ax-by)}-1$. Mà $P(m+ax-by) \in \lbrace P(1);P(2);...;P(d) \rbrace$ nên
\[ M<3^{P(m+ax-by)} \le 3^{\max \lbrace P(1);P(2);...;P(d) \rbrace}: \textrm{ trái } \eqref{1}\]
Vậy $Q(x)$ bị chặn hay $Q(x)$ là đa thức hằng.

[PSW]

Chấm điểm:
hxthanh: 50 điểm

perfectstrong: 5 điểm

Trungpbc: 10 điểm