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

[hxthanh]

Với $n$ là số nguyên dương

Chứng minh đẳng thức sau:

$\sum_{i=0}^n\sum_{k=0}^i \left[(i-k)\binom{n}{i}\binom{n}{k}\right] = \dfrac{n}{2}\binom{2n}{n}$

[supermember]

Bài này khó và tương đối dài ; mình sẽ post mỗi ngày 1 phần

Phần 1: Dễ nhận thấy đẳng thức sau đây:

$\sum _{0 \le k \le i \le n} (i-k)\binom{n}{i}\binom{n}{k}$

$ = \sum _{k=0}^{n-1} \left \{ \binom{n}{0} +\binom{n}{1} + \cdots + \binom{n}{k} \right \} \cdot \left \{ \binom{n}{k+1} + \binom{n}{k+2}+ \cdots +\binom{n}{n} \right \} = a_{n-1}$

Với một số nguyên dương $n$ cho trước . Xét dãy số $ \left ( b_k \right )_{k \ge 0}$ xác định như sau:

$ b_k = \binom{n}{0} +\binom{n}{1} + \cdots + \binom{n}{k}$

Bây giờ xét khai triễn chuỗi luỹ thừa hình thức của : $\mathcal{C} (x) = \frac{(1+x)^n}{1-x} $ ; với $ |x| <1$

Phần 2 :
Ta có : $\mathcal{C} (x) = \left ( 1+x+x^2 + x^3+ \cdots \right )\left ( \binom{n}{0}+ \binom{n}{1} x + \cdots+ \binom{n}{n}x^n\right ) = \sum _{n=0}^{\infty} c_n x^n$

Bằng cách xem xét hệ số của $x^k \ \ ; 0 \le k \le n$ ; ta có : $ b_k = c_k \ \ \forall \ \ 0 \le k \le n$
$ \Rightarrow \left ( \mathcal{C} (x) \right )^2 = \frac{(1+x)^{2n}}{(1-x)^2} = \left ( \sum _{n=0}^{\infty} c_n x^n \right ) \cdot \left ( \sum _{n=0}^{\infty} c_n x^n \right )$

$ \Rightarrow \left ( \binom{2n}{0}+ \binom{2n}{1} x + \cdots+ \binom{2n}{2n}x^{2n} \right ) \cdot \left ( 1+ 2x + 3x^2 +... \right ) = \left ( \sum _{n=0}^{\infty} c_n x^n \right ) \cdot \left ( \sum _{n=0}^{\infty} c_n x^n \right )$

Bây giờ so sánh hệ số của $x^{n-1}$ ở $2$ vế ; ta có :

$\sum _{r=0}^{n-1} \binom{2n}{r}\left ( n-r \right ) = c_0 c_{n-1} + c_1 c_{n-2} +...+ c_{n-1}{c_0} $

$ = b_0 b_{n-1} + b_1 b_{n-2} +...+ b_{n-1} b_0 $

$ = \sum _{k=0}^{n-1} \left \{ \binom{n}{0} +\binom{n}{1} + \cdots + \binom{n}{k} \right \} \cdot \left \{ \binom{n}{k+1} + \binom{n}{k+2}+ \cdots +\binom{n}{n} \right \} = a_{n-1}$

Phần 3 : Như vậy; công việc còn lại của ta là đi chứng minh đẳng thức:
$\sum _{r=0}^{n-1} \binom{2n}{r}\left ( n-r \right )=\frac{n}{2}\binom{2n}{n} \ \ (1)$

Ai màu mè một chút thì có thể thử tài đếm $2$ cách với cái đẳng thức này; tuy nhiên mình tiếp tục theo hướng biến đổi đại số ; thật vậy:

$\sum _{r=0}^{n-1} \binom{2n}{r}\left ( n-r \right )= n\sum _{r=0}^{n-1} \binom{2n}{r} - \sum _{r=0}^{n-1} r \binom{2n}{r}$

$ = \frac{n}{2}\left ( \sum _{r=0}^{2n} \binom{2n}{r} - \binom{2n}{n}\right )- \sum _{r=0}^{n-1} r \binom{2n}{r}$

$ = n \cdot 2^{2n-1} - \frac{n}{2} \cdot\binom{2n}{n} - \sum _{r=0}^{n-1} r \binom{2n}{r}$

Nên đẳng thức $(1)$ sẽ tương đương với :

$ n \cdot 2^{2n-1} = \sum _{r=0}^{n} r \binom{2n}{r} \ \ (2)$

Phần 4: Bây giờ với $ r = 1 ; 2 ; ... ; n $ ; ta có :

$r \binom{2n}{r}= \frac{r \cdot (2n)!}{r! \cdot (2n-r)!}= \frac{(2n)!}{(r-1)! \cdot (2n-r)!} = \frac{ 2n \cdot(2n-1)!}{(r-1)! \cdot (2n-r)!} = 2n \binom{2n-1}{r-1}$

Suy ra : $\sum _{r=0}^{n} r\binom{2n}{r} = 2n \sum _{r=1}^{n}\binom{2n-1}{r-1}= 2n\sum _{r=0}^{n-1}\binom{2n-1}{r} = 2n \cdot \frac{1}{2} \cdot \sum _{r=0}^{2n-1}\binom{2n-1}{r} = n \cdot 2^{2n-1} $

Từ đây suy ra $(2)$ đúng ; suy ra $(1)$ đúng ; và do đó ; đẳng thức ban đầu được chứng minh hoàn toàn

Một bài Toán rất đẹp

@ thầy Thanh: sau khi em giới thiệu bài này trên 1 diễn đàn; có 1 vài gã Tây có PM hỏi em hướng làm. Nếu thầy có thời gian thì tổng hợp hộ em các cách giải cho bài này vào 1 file PDF và trình bày bằng tiếng Anh nhé. Có gì em đi " trao đổi" với mấy tay ấy
______
@psw: Ý tưởng hay đấy!

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 29-10-2012 - 19:42
reply

[hxthanh]

Cách tính công phu vậy mà supermember cũng nghĩ ra được thì quả là đáng nể!
Sau đây là cách làm khá sơ cấp của tôi


Lời giải

Thuần tuý Đại Số (Một vài phương pháp tính tổng)

\begin{equation}S=\sum_{i=0}^n\sum_{k=0}^i \left[(i-k)\binom{n}{i}\binom{n}{k}\right] = \sum_{i=0}^n\left(\binom{n}{i}\left[i\sum_{k=0}^i \binom{n}{k}-\sum_{k=0}^i k\binom{n}{k} \right]\right) \label{eq:pt1}\end{equation}
$\Rightarrow S=\sum_{i=0}^n\left(\binom{n}{i}\left[i\sum_{k=0}^i \binom{n}{k}-\sum_{k=1}^i \dfrac{k.n!}{k!(n-k)!} \right]\right)$

$\Rightarrow S=\sum_{i=0}^n\left(\binom{n}{i}\left[i\sum_{k=0}^i \binom{n}{k}-\sum_{k=1}^i \dfrac{n!(n+1-k)}{(k-1)!(n-k)!} \right]\right)$

$\Rightarrow S=\sum_{i=0}^n\left(\binom{n}{i}\left[i\sum_{k=0}^i \binom{n}{k}+(n-i)\binom{n}{i}-\sum_{k=0}^i (n-k)\binom{n}{k}\right]\right)$

Cộng đẳng thức này vế theo vế với $\boxed{\ref{eq:pt1}}$ ta được
\begin{equation}S= \sum_{i=0}^n\left(\dfrac{1}{2}\binom{n}{i}\left[(n-i)\binom{n}{i}+(2i-n)\sum_{k=0}^i \binom{n}{k}\right]\right) \label{eq:pt2}\end{equation}
Ta sẽ chứng minh rằng:
\begin{equation} S= \sum_{i=0}^n\sum_{k=0}^i \left[(i-k)\binom{n}{i}\binom{n}{k}\right]=\sum_{i=0}^n\sum_{k=0}^i \left[(2i-n)\binom{n}{i}\binom{n}{k}\right]\label{eq:pt3}\end{equation}

hay \begin{equation}A=\sum_{0\le k\le i \le n} \left[(n-i-k)\binom{n}{i}\binom{n}{k}\right] =\sum_{0\le i\le k \le n} \left[(n-i-k)\binom{n}{i}\binom{n}{k}\right]=0\label{eq:pt4}\end{equation}
$\qquad\qquad\qquad\qquad\qquad\qquad$ (Do $i, k$ có tính đối xứng)

Mặt khác ta cũng có: \begin{equation} \sum_{0\le i+k=t \le 2n} \left[(n-t)\binom{n}{i}\binom{n}{k}\right]+\sum_{t=0}^{n} \left[(n-2t)\binom{n}{t}^2\right] =\sum_{0\le k\le i \le n} \left[(n-i-k)\binom{n}{i}\binom{n}{k}\right]+\sum_{0\le i\le k \le n} \left[(n-i-k)\binom{n}{i}\binom{n}{k}\right]=2A\label{eq:pt5}\end{equation}
Ta có: $X=\sum_{0\le i+k=t \le 2n} \left[(n-t)\binom{n}{i}\binom{n}{k}\right]=\sum_{0\le i+k=t \le 2n} \left[(t-n)\binom{n}{i}\binom{n}{k}\right]=-X\Rightarrow X=0\quad$
$\quad$(Thay $t$ bởi $2n-t$ - Đảo chiều)
Tương tự: $Y=\sum_{t=0}^{n} \left[(n-2t)\binom{n}{t}^2\right]=\sum_{t=0}^{n} \left[(2t-n)\binom{n}{n-t}^2\right]=-Y\Rightarrow Y=0\quad$ (Thay $t$ bởi $n-t$ - Đảo chiều)

Thay các kết quả này vào

$\boxed{\ref{eq:pt5}}$ ta chứng minh được $A=0$

Cộng biểu thức của $A$ vào vế phải của $\boxed{\ref{eq:pt3}}$ ta chứng minh được $\boxed{\ref{eq:pt3}}$

Như vậy từ

$\boxed{\ref{eq:pt2}}$, ta có:

$ S=\dfrac{1}{2}\sum_{i=0}^n \left[(n-i)\binom{n}{i}^2\right]+\dfrac{1}{2}\sum_{i=0}^n\sum_{k=0}^i
\left[(2i-n)\binom{n}{i}\binom{n}{k}\right] = \dfrac{1}{2}\sum_{i=0}^n \left[i\binom{n}{n-i}^2\right]+\dfrac{1}{2}S$
(Thay $i$ bởi $n-i$ - Đảo chiều)
Rồi bây giờ ta có:
$S=\sum_{i=0}^n \left[(n-i)\binom{n}{i}^2\right]=\sum_{i=0}^n \left[i\binom{n}{i}^2\right]$
Suy ra
$S=\dfrac{n}{2}\sum_{i=0}^n \left[\binom{n}{i}^2\right]$

... Đến đây bài toán đã được hoàn thành 99%

$S=\dfrac{n}{2}\sum_{i=0}^n \left[\binom{n}{i}^2\right]=\dfrac{n}{2}\sum_{i=0}^n \left[\binom{n}{i}\binom{n}{n-i}\right]=\dfrac{n}{2}\sum_{i+j=n}\left[\binom{n}{i}\binom{n}{j}\right]=\dfrac{n}{2}\binom{2n}{n}$

Bài toán được giải quyết hoàn toàn (Vất vả hơn cả cách của supermember)

[hxthanh]

Còn một cách nữa, nhưng mà khó diễn đạt bằng ngôn ngữ sơ cấp để hiểu - nên thôi!

Bài toán này giải quyết xong mà thu được khá nhiều bổ đề, bài toán mới cũng hay hay. Chỉ có điều không dùng được công cụ đếm theo hai cách mới buồn!
Bạn nào tìm được cách chứng minh sử dụng đếm bằng 2 cách thì post lên nhé!