Đến nội dung

Hình ảnh

$\sum_{k=0}^n\dfrac{{n\choose k}^2}{n+k\choose k}=?$

- - - - - đẳng thức tổ hợp

  • Please log in to reply
Chủ đề này có 2 trả lời

#1
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết
Bài toán:
Chứng minh đẳng thức:

$\sum_{k=0}^n\dfrac{{n\choose k}^2}{n+k\choose k}=\dfrac{n!(3n)!}{\left[(2n)!\right]^2}$

@Dark templar: Em công nhận là anh Lộc nói đúng,anh nghiện cái này mất rồi :))

@hxthanh: Ơ thế đang tập trung vào chuyên đề này thì không được "nghiện" à?

@ supermember: bài này nhìn cũng đẹp đấy; khà khà

Mà phán như ở dưới cũng hơi " oan" cho Phúc ; từ lúc Post đề tới lúc thầy Post bài giải chỉ cách nhau có vài tiếng thôi mà >:)

@Dark templar:Anh Thanh nói oan em thật,nãy giờ em đi chơi Giáng Sinh với Kiên mà,làm gì có thời gian suy nghĩ bài này :(

Bài viết đã được chỉnh sửa nội dung bởi dark templar: 25-12-2012 - 22:07


#2
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết

Bài toán:
Chứng minh đẳng thức:

$\sum_{k=0}^n\dfrac{{n\choose k}^2}{n+k\choose k}=\dfrac{n!(3n)!}{\left[(2n)!\right]^2}$

Bài này là một sự kết hợp linh hoạt trong việc biến đổi đại số và SPTP liên tiếp. Thật lấy làm tiếc khi cu dark templar không xử được nó.
Ta có:
Đẳng thức đã cho tương đương với:
$\qquad\sum_{k=0}^n \dfrac{n!n!}{k!k!(n-k)!(n-k)!}\cdot\dfrac{k!n!}{(n+k)!}=\dfrac{n!(3n)!}{(2n)!(2n)!}$
$\Leftrightarrow \dfrac{n!n!}{(2n)!}\sum_{k=0}^n \dfrac{n!}{k!(n-k)!}\cdot\dfrac{(2n)!}{(n-k)!(n+k)!}=\dfrac{n!(3n)!}{(2n)!(2n)!}$
$\Leftrightarrow \sum_{k=0}^n {n\choose k}{2n\choose n-k}={3n\choose n}$

Đẳng thức trên đúng theo Vandermonde, ở đây ta dùng SPTP cho đỡ thèm! :))

$\Leftrightarrow S=\sum_{k=0}^n {n\choose k}{2n\choose k}={3n\choose n}\quad\text{(đảo chiều)}$
Đến đây các bạn chú ý rằng $(-1)^k.(-1)^k=1$
Ta có:
$\left\{\begin{align*}&(-1)^k{n\choose k}=\Delta\left[(-1)^{k-1}{n-1\choose k-1}\right]\\&\Delta\left[(-1)^k{2n\choose k}\right]=(-1)^{k+1}{2n+1\choose k+1}\end{align*}\right.$
Do đó áp dụng SPTP, ta được:
$\begin{eqnarray*}S&=&(-1)^{k-1}{n-1\choose k-1}(-1)^k{2n\choose k}\Bigg|_{k=0}^{n+1}-\sum_{k=0}^n (-1)^{k+1}{2n+1\choose k+1}(-1)^k{n-1\choose k}\\&=&\sum_{k=0}^{n-1}{n-1\choose k}{2n+1\choose k+1}\end{eqnarray*}$
Các bạn có nhận ra sự thay đổi sau 1 lần SPTP không?
Nếu cứ tiếp tục áp dụng SPTP thì sau $n$ bước ta sẽ có:
$S=\sum_{k=0}^{n-n}{n-n\choose k}{2n+n\choose k+n}={3n\choose n}$
Và đẳng thức được chứng minh!

Để cho chặt chẽ hơn ta có thể chứng minh rằng:
$S_{m,n}=\sum_{k=0}^{n-m}{n-m\choose k}{2n+m\choose k+m}=S_{m+1,n}=...=S_{n,n}={3n\choose n}$
_______________________________
(Trích tuyển tập ĐTTH VMF 2013)

#3
gogo123

gogo123

    Trung sĩ

  • Thành viên
  • 102 Bài viết

Bài này là một sự kết hợp linh hoạt trong việc biến đổi đại số và SPTP liên tiếp. Thật lấy làm tiếc khi cu dark templar không xử được nó.
Ta có:
Đẳng thức đã cho tương đương với:
$\qquad\sum_{k=0}^n \dfrac{n!n!}{k!k!(n-k)!(n-k)!}\cdot\dfrac{k!n!}{(n+k)!}=\dfrac{n!(3n)!}{(2n)!(2n)!}$
$\Leftrightarrow \dfrac{n!n!}{(2n)!}\sum_{k=0}^n \dfrac{n!}{k!(n-k)!}\cdot\dfrac{(2n)!}{(n-k)!(n+k)!}=\dfrac{n!(3n)!}{(2n)!(2n)!}$
$\Leftrightarrow \sum_{k=0}^n {n\choose k}{2n\choose n-k}={3n\choose n}$

Cho em tham gia với thầy hxthanh ơi! Thầy thanh giải bá đạo quá, nhất là mấy bài bên topic kia.
Đến đoạn này em giải bằng hàm sinh như sau:
Chú ý khai triển sau: $$\frac{1}{(1-x)^{n+1}}=\sum_{k=0}^{\infty }\binom{n+k}{k}x^{k}$$
Xét hàm sinh của đề bài:
$$F(x)=\sum_{n=0}^{\infty }\sum_{k=0}^{n}\binom{n}{k}\binom{2n}{k}x^{2n}$$
$=\sum_{k=0}^{n}\binom{n}{k} x^{k}\sum_{2n=k}^{\infty }\binom{2n}{2n-k}x^{2n-k}$
$=\sum_{k=0}^{n}\binom{n}{k} x^{k}.\frac{1}{(1-x)^{k+1}}$
$=\frac{1}{1-x}. \left ( \frac{x}{1-x}+1 \right )^{n}=\frac{1}{(1-x)^{n+1}}$
$=\sum_{k=0}^{\infty }\binom{n+k}{k}x^{k}$
Suy ra hệ số của $x^{2n}$ trong khai triển $F(x)$ là $\binom{3n}{2n}=\binom{3n}{n}$ hay $\sum_{k=0}^n {n\choose k}{2n\choose n-k}={3n\choose n}$
Vậy ta có điều phải chứng minh.

LKN-LLT






Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: đẳng thức, tổ hợp

0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh