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^+}$
$\sum_{k=0}^n 2^kC_n^kC_{n-k}^{\frac{n-k}{2}}=C_{2n+1}^n$
#1
Đã gửi 25-08-2016 - 22:41
#2
Đã gửi 25-08-2016 - 23:05
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
#3
Đã gửi 29-08-2016 - 17:48
Đế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
- L Lawliet, bangbang1412 và baopbc thích
For the love of Canidae
#4
Đã gửi 31-08-2016 - 23:55
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.
- redfox yêu thích
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh