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

[I Love MC]

Chứng minh rằng : $\sum_{k=0}^n 2^kC_n^kC_{n-k}^{\frac{n-k}{2}}=C_{2n+1}^n ,   \forall n \in \mathbb{Z^+}$

[HoaiBao]

Chứng minh rằng : $\sum_{k=0}^n 2^kC_n^kC_{n-k}^{\frac{n-k}{2}}=C_{2n+1}^n ,   \forall n \in \mathbb{Z^+}$

mình nghĩ chỗ $\frac{n-k}{2}$ phải là phần nguyên mới được

[redfox]

Đếm bằng hai cách. Chọn $n$ phần tử từ $2n+1$ phần tử. Dễ có vế phải.

Chia $2n$ phần tử trong $2n+1$ phần tử thành $n$ cặp $(a_1;b_1);(a_2;b_2);...;(a_n;b_n)$

Giả sử có $k$ cặp chứa đúng $1$ phần tử trong $n$ cặp. Có $2^k\binom{n}{k}$ cách chọn $k$ phần tử (chọn $k$ cặp rồi chọn phần tử $a_i$ hoặc $b_i$).

Còn lại $\left \lfloor \frac{n-k}{2} \right \rfloor$ cặp chứa $2$ phần tử được chọn trong $n-k$ cặp còn lại. Có $\binom{n-k}{\left \lfloor \frac{n-k}{2} \right \rfloor}$ cách chọn.

Phần tử còn lại chọn hay không sao cho đủ $n$ phần tử, có $1$ cách chọn.

Vậy có $2^k\binom{n}{k}\binom{n-k}{\left \lfloor \frac{n-k}{2} \right \rfloor}$ cách chọn có $k$ cặp chứa đúng $1$ phần tử được chọn. Cho $k$ từ $0$ đến $n$ ta có vế trái.

(Q.E.D)

Có ai có cách khác không?

Bài viết đã được chỉnh sửa nội dung bởi redfox: 29-08-2016 - 17:50

[HoaiBao]

Cách giải khác :

Ta có hai trường hợp cần phải xét:

Trường hợp I: $n$ là số lẻ hay đặt $n=2m+1$

$\sum_{k=0}^{2m+1}2^k \binom{2m+1}{k} \binom{2m+1-k}{[\frac{2m+1-k}{2}]}$

$=\sum_{k=0}^{m}2^{2k} \binom{2m+1}{2k} \binom{2m+1-2k}{[\frac{2m+1-2k}{2}]}+\sum_{k=0}^{m}2^{2k+1} \binom{2m+1}{2k+1} \binom{2m+1-2k-1}{[\frac{2m+1-2k-1}{2}]}$

$=\sum_{k=0}^{m}2^{2k} \binom{2m+1}{2k} \binom{2m-2k+1}{m-k}+\sum_{k=0}^{m}2^{2k+1} \binom{2m+1}{2k+1} \binom{2m-2k}{m-k}$

$=\frac{1}{2}\sum_{k=0}^{m}2^{2k} \binom{2m+1}{2k} \binom{2m-2k+2}{m-k+1}+\sum_{k=0}^{m}2^{2k+1} \binom{2m+1}{2k+1} \binom{2m-2k}{m-k}$

$=\frac{1}{2}[t^{m+1}]\frac{1}{\sqrt{1-4t}}.\frac{(1+2\sqrt{t})^{2m+1}+(1-2\sqrt{t})^{2m+1}}{2}+\frac{1}{\sqrt{t}}[t^{m}]\frac{1}{\sqrt{1-4t}}.\frac{(1+2\sqrt{t})^{2m+1}-(1-2\sqrt{t})^{2m+1}}{2}$

$=\frac{1}{2}[t^{m+1}]\frac{1}{\sqrt{1-4t}}.\frac{(1+2t)^{2m+2}+(1-2t)^{2m+2}}{2}$

$=\frac{1}{2}.\sum_{k=0}^{m+1}2^{2k}\binom{2m+2}{2k}\binom{2m-2k+2}{m-k+1}$

$=\frac{1}{2}.\sum_{k=0}^{m+1}2^{2m-2k+2}\binom{2m+2}{2k}\binom{2k}{k}$

$=\frac{1}{2}[t^{2m+2}]\frac{1}{1-2t}.[\frac{1}{\sqrt{1-4u}}|u=\frac{t^2}{(1-2t)^2}]$

$=\frac{1}{2}[t^{2m+2}]\frac{1}{\sqrt{1-4t}}$

$=\frac{1}{2}\binom{4m+4}{2m+2}$

$=\binom{4m+3}{2m+1}=\binom{2n+1}{n}$

Tương tự với trường hợp 2: n chẵn.

Do đó ta có được điều phải chứng minh.

--------------------------------------------------------------------

P/s: Lời giải hơi rờm rà tí. 

 

Có ai còn cách khác nữa không.