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}$
$\sum_{0 \le k \le i \le n} \left[(i-k)\binom{n}{i}\binom{n}{k}\right] = \dfrac{n}{2}\binom{2n}{n}$
#1
Đã gửi 15-10-2012 - 12:43
- supermember, HÀ QUỐC ĐẠT, batigoal và 4 người khác yêu thích
#2
Đã gửi 26-10-2012 - 11:16
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
- perfectstrong, hxthanh, Mai Duc Khai và 4 người khác yêu thích
#3
Đã gửi 28-10-2012 - 20:26
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)
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)
- perfectstrong, Zaraki, The Gunner và 9 người khác yêu thích
#4
Đã gửi 29-10-2012 - 16:48
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é!
- The Gunner, Sagittarius912, I love Math forever và 5 người khác yêu thích
Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: supermember
Toán thi Học sinh giỏi và Olympic →
Dãy số - Giới hạn →
Bài toán đáp lễ supermember $\mathbb{F}_n(x)=...$Bắt đầu bởi hxthanh, 13-07-2022 supermember, psw |
|
|||
Toán thi Học sinh giỏi và Olympic →
Tổ hợp và rời rạc →
Một bài tổ hợp từ một bài số họcBắt đầu bởi Karl Heinrich Marx, 26-03-2017 supermember |
|
|||
pom
Cửa sổ Diễn Đàn Toán Học →
Những sự kiện đã kết thúc →
Thi đấu giải Toán →
Những bài toán trong tuần →
Bài toán tháng 8/2014 - Trò chơi Đoán SốBắt đầu bởi hxthanh, 22-06-2014 pom, e. galois, supermember |
|
|||
Toán thi Học sinh giỏi và Olympic →
Dãy số - Giới hạn →
CMR: $2S=3F_nF_{n+1}^2-F_n^3-F_{n+1}^3+1$Bắt đầu bởi hxthanh, 18-11-2012 fibonacci, supermember |
|
|||
Toán thi Học sinh giỏi và Olympic →
Tổ hợp và rời rạc →
$\sum_{k=0}^n \left[\sum_{j=0}^k \binom{n}{j}\right]^2=(n+2)2^{2n-1}-\dfrac{n}{2}\binom{2n}{n}$Bắt đầu bởi hxthanh, 29-10-2012 supermember, the gunner và . |
|
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh