Bài 1:(Tổ hợp)
Chứng minh rằng với mọi $n$ nguyên dương ta có:
$\sum_{k=0}^{m}C^k_{n+k}2^{m-k}+\sum_{k=0}^{n}C^k_{m+k}2^{n-k}=2^{m+n+1}$
Đếm bằng hai cách
Ta sẽ đếm số tập con của tập có m+n+1 phần tử
Xét Tập $X = {1, 2,...., m+n+1}$
Cách 1: Đếm số tập con của X là $2^{m+n+1}$
Cách 2: Ta sẽ phân hoạch tập con của X thành 2 loại I và II
* Loại I: là các tập con có dạng $A = {x_{1}, x_{2}, x_{3},...., x_{n+i}}$ Trong đó $1 \leqslant i \leqslant m+1$
Không mất tính tổng quát giả sử $x_{1} < x_{2} < x_{3} < ... < x_{n+i}$ khi đó $x_{n+1} = n+1+k$ với $0 \leqslant k \leqslant m$
Để thiết lập tập con A ta thực hiện các bước sau:
Bước I: Chọn n phần từ bất kì từ n+k phần tử, có tất cả $\begin{pmatrix} n+k\\n \end{pmatrix}$
Bước II:rồi ta thêm một số tập con của tập $ {n+k+2, n+k+3,....n+m+1}$ có $2^{m-k}$ cách thêm Như vậy có tất cả: $\begin{pmatrix} n+k\\n \end{pmatrix}.2^{m-k}$ tập A có số phần tử lớn hơn n
Loại II: tương tự ta cũng tính được $\begin{pmatrix} m+k\\n \end{pmatrix}.2^{n-k}$ tập con có số phần tử lớn hơn m, tương ứng mỗi tập con có số phần tử lớn hơn m ta tìm được tập con có số phàn tử không quá n
Như vậy số tập con của X bằng $\begin{pmatrix} m+k\\n \end{pmatrix}.2^{n-k}$ + $\begin{pmatrix} n+k\\n \end{pmatrix}.2^{m-k}$
Hay $\begin{pmatrix} m+k\\n \end{pmatrix}.2^{n-k}$ + $\begin{pmatrix} n+k\\n \end{pmatrix}.2^{m-k}$ = $2^{m+n+1}$
Bài viết đã được chỉnh sửa nội dung bởi longnguyenviet141: 01-11-2015 - 23:40