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

[hxthanh]

Với $n$ nguyên dương cho trước:
Chứng minh rằng: $$\sum_{k=0}^n C_{2k}^{\;k}C_{2n-2k}^{\;n-k}=4^n$$
________________________________________
Note: $C_{n}^{\;k}=\binom{n}{k}=\dfrac{n!}{k!(n-k)!}$

[PSW]

Cho em cắm rùi ; đấu thầu bài này

Phần 1 :

Xét khai triển chuỗi luỹ thừa hình thức dựa trên định lý Khai triển nhị thức suy rộng :

$\mathcal{A} (x) = \dfrac{1}{\sqrt{1-x}} = (1+(-x))^{-1/2}$

$ = \sum\limits_{n=0}^{\infty} \left(\begin{matrix} -\dfrac{1}{2}\\ \\ n\end{matrix}\right) (-x)^n$ ; với $ |x| <1$

Trong đó : $ \left(\begin{matrix} -\dfrac{1}{2}\\ \\ n\end{matrix}\right) = 1 $ nếu $n =0$

Còn khi $ n \ge 1$ thì :


$\begin{align*}
\left(\begin{matrix} -\dfrac{1}{2}\\ \\ n\end{matrix}\right) &= \dfrac{-\dfrac{1}{2}\left ( -\dfrac{1}{2} -1 \right )\left ( -\dfrac{1}{2} -2 \right )\cdots \left ( -\dfrac{1}{2} -n+1 \right )}{n!} \\
&= \dfrac{(-1)^n (2n-1)!!}{2^n \cdot n!} \\
&= \dfrac{(-1)^n n! \cdot 2^n . (2n-1)!!}{4^n \cdot (n!)^2} \\
&= \dfrac{(-1)^n (2n)!! \cdot (2n-1)!!}{4^n \cdot (n!)^2} \\
&= \dfrac{(-1)^n (2n)!}{4^n \cdot (n!)^2} \\
&= \dfrac{(-1)^n}{4^n}\binom{2n}{n} \end{align*}$

Suy ra : $\mathcal{A}(x) = \sum\limits_{n=0}^{\infty} a_n x^n$

Với $ a_n = \dfrac{1}{4^n}\binom{2n}{n},\;\; \forall n \in \mathbb{N}$

Bài viết đã được chỉnh sửa nội dung bởi PSW: 18-12-2011 - 00:03

[PSW]

Phần 2 : ( Tối nay làm tiếp ; mệt mệt =.=)

Sao cái Latex tự nhiên xấu đau xấu đớn =.=

Sài Gòn đêm nay lạnh ngắt ; muỗi nó còn chui luôn trong hang ; nghỉ kiếm ăn . Người vẫn ...

Ta có : $\left ( \mathcal{A} (x) \right )^2 = \left ( \sum\limits_{n=0}^{\infty} a_n x^n \right )^2 = \dfrac{1}{1-x} = \sum\limits_{n=0}^{\infty} x^n \ \ ( |x| <1)$

Nên nếu vận dụng tính chất của 2 chuỗi số bằng nhau ; ta có thể đồng nhất hệ số $x^n$ như sau :

$1 = \sum\limits_{k=0}^{n} a_k \cdot a_{n-k} = \sum\limits_{k=0}^{n} \dfrac{1}{4^k}\binom{2k}{k}\dfrac{1}{4^{n-k}}\binom{2n-2k}{n-k} $

$ = \dfrac{1}{4^n}\sum\limits_{k=0}^{n}\binom{2k}{k}\binom{2n-2k}{n-k}$

$\implies 4^n= \sum\limits_{k=0}^{n}\binom{2k}{k}\binom{2n-2k}{n-k}$

Và đây là điều phải chứng minh

Xin lỗi thầy Thanh nhá ; dạo này em chỉ toàn ăn với ngủ nên quên béng vụ cắm dùi :">

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 18-12-2011 - 14:29

[Nguyễn Hưng]

Có ai giải được bằng phương pháp đếm bằng hai cách của Tổ hợp không ạ? Em rất thích phương pháp đó

[hxthanh]

Vất vả cho PSW quá (muỗi còn phải ngủ nữa là ...

[E. Galois]

Thầy Thanh có một bộ tú lơ khơ phong cách hxthanh. Bộ tú này cũng giống các bộ tú khác là có 4 chất cơ, rô, pích, nhép. Đặc biệt ở chỗ, bộ tú này gồm các quân bài từ $1, 2, 3, ..., n$ thay vì $A, 2, 3, ..., J, Q, K$ như bộ bài thường. Đối với quân bài ${\color{Red} \blacklozenge \color{Red} \blacklozenge }$ (Hai Rô) ta gọi Hai là phần Số; Rô là phần Chất

Dễ thấy bộ tú của thầy Thanh có $4n$ quân bài.

Thầy Thanh định lấy từ bộ bài của mình ra $2n$ quân bài sao cho có đúng 2 quân Một, 2 quân Hai, 2 quân Ba, ... 2 quân $n$.

Thầy làm như sau:
- Thầy chia bộ bài của mình ra làm $2n$ đôi, mỗi đôi gồm 2 quân bài cùng Số. Số cách chia như vậy ta không quan tâm . Sau đó, thầy có 2 cách

- Cách làm 1. Thầy thực hiện $2n$ hành động. Ở hành động thứ $i, (i = 1, 2, ..., 2n)$ thầy chọn ra 1 quân bài từ đôi $i$. Có 2 cách chọn.
Vậy theo quy tắc nhân, thầy có: $2^{2n} = 4^n$ cách.

- Cách làm 2. Thầy chia $2n$ đôi thành hai phần, mỗi phần có một số chẵn đôi, thầy lấy một nửa ở mỗi phần. số cách làm là:
$$\sum_{k=1}^{n}C_{2k}^{k}.C_{2n-2k}^{n-k}$$
Vậy:
$$\sum_{k=1}^{n}C_{2k}^{k}.C_{2n-2k}^{n-k} = 4^n$$

p/s: Không biết có sai nữa ko

[hxthanh]

Hay quá! Mình cũng hy vọng tìm được cách giải thích sơ cấp như trên, mà vẫn không nghĩ ra! Cảm ơn thầy Thế nhiều

[Peter Pan]

Ta có thể đếm theo cách khác như sau: một đoạn thẳng có độ dài $n$ được tô bằng 4 màu, Đ,X,V,T. rõ ràng ta có $4^n$ cách như thế
bây giờ ta đếm theo cách khác như sau: ta sẽ chọn ra một tập cách tô màu Đ và X sao cho $Đ+X=k$. thì số cách chọn sẽ là
$\sum_{i=0}^kC_i^kC_k^{k-i}=C_{2k}^k$
khi đó số cách chọn ra các đoạn màu V,T sẽ là $\sum_{j=0}^kC_{n-k}^jC_{n-k}^{k-j}=C_{2n-2k}^{n-k}$
do đó với mỗi $k$ cố định thì ta được số cách tô sẽ là $C_{2k}^{k}C_{2n-2k}^{n-k}$. Cho $k$ chạy từ 0 đến $n$ ta được số cách tô màu là$\sum_{i=0}^nC_{2k}^{k}C_{2n-2k}^{n-k}$
=>đpcm

[PSW]

Quá tuyệt ; thật không hổ danh người mà mình đã tiến cử ngay từ đầu làm CTV Olympic :X

[Crystal]

Một ý tưởng từ bài toán trên.

Bài toán. Chứng minh rằng với mọi số tự nhiên $n \ge 2$ ta có $\sum\limits_{k = 0}^{n - 1} {C_{2n + 1}^{2\left( {n - k} \right)}C_{n - k}^1} $ chia hết cho ${4^{n - 1}}$.

[perfectstrong]

Một cách giải khác cũng dùng hàm sinh
Lời giải:
Định lý B: Cho $b<0$, khi đó:
\[
\sum\limits_k {\binom{n + ak}{m + bk}f_k } = \left[ {t^m } \right]\left( {1 + t} \right)^n f\left( {t^{ - b} \left( {1 + t} \right)^a } \right)
\]
===================================
\[
\begin{array}{rcl}
\sum\limits_{k = 0}^n {\binom{2k}{k}\binom{2n - 2k}{n - k}} &\mathop = \limits^B & \left[ {t^n } \right]\left( {1 + t} \right)^{2n} \left[ {f\left( {\frac{t}{{\left( {1 + t} \right)^2 }}} \right) | f\left( x \right) = \frac{1}{{\sqrt {1 - 4x} }}} \right] \\
&=& \left[ {t^n } \right]\left( {1 + t} \right)^{2n} .\frac{1}{{\sqrt {1 - \frac{{4t}}{{\left( {1 + t} \right)^2 }}} }} \\
&=& \left[ {t^n } \right]\left( {1 + t} \right)^{2n} .\frac{{1 + t}}{{1 - t}} \\
&=& \left[ {t^n } \right]\frac{{\left( {1 + t} \right)^{2n + 1} }}{{1 - t}} \\
&=& \left[ {t^n } \right]\sum\limits_{k = 0}^{2n + 1} {\binom{2n + 1}{k}t^k } \sum\limits_{h = 0}^\infty {t^h } \\
&=& \sum\limits_{k = 0}^n {\binom{2n + 1}{k}} = \frac{1}{2}\sum\limits_{k = 0}^{2n + 1} {\binom{2n + 1}{k}} = \frac{1}{2}.2^{2n + 1} = 4^n\\
\end{array}
\]

Một lời giải khác, cũng dùng hàm sinh:
Định lý Convolution:
\[
\left[ {t^n } \right]f\left( t \right)g\left( t \right) = \sum\limits_{k = 0}^n {\left\{ {\left[ {t^k } \right]f\left( t \right)} \right\}\left\{ {\left[ {t^{n - k} } \right]g\left( t \right)} \right\}}
\]
===================================
Áp dụng:
$$\begin{array}{l}
\sum\limits_{k = 0}^n {\binom{2k}{k}\binom{2\left( {n - k} \right)}{n - k}}\\
\mathop = \limits^{con} \left[ {t^n } \right]\left[ {f\left( t \right)g\left( t \right)|f\left( x \right) = \frac{1}{{\sqrt {1 - 4x} }};g\left( x \right) = \frac{1}{{\sqrt {1 - 4x} }}} \right] \\
= \left[ {t^n } \right]\frac{1}{{1 - 4t}} = \left[ {t^n } \right]\sum\limits_{k = 0}^\infty {\left( {4t} \right)^k } = 4^n
\end{array}$$
@supermember: Giỏi quá :X
@perfectstrong: nhờ tài liệu của anh Lộc viết hay

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 02-03-2013 - 21:45