Bài toán: Xét tập A=\{1;2;...;n\}. Với bất kì tập con khác rỗng M của A, M=\left \{ m_1;m_2,...,m_k \right \}, m_1 > m_2 > ... > m_k Đặt S(M) = m_1 - m_2 + m_3 +... + (-1)^{k+1}m_k Tính S = \sum_{M \subset A}S(M)
Lời giải:
Ta ký hiệu lại như sau:
Tổng cần tính là S_n=\sum_{k=1}^n f(k,n) với f(k,n) là tổng đan dấu các phần tử của mỗi tập con, tất cả các tập con có k phần tử của A trong đó phần tử lớn nhất mang dấu (+)
Ta sẽ chứng minh f(k,n)=\left\lfloor\frac{k+1}{2}\right\rfloor {n+1\choose k+1}\quad(k\le n)\qquad(1)
Rồi từ đó suy ra tổng cần tính là:
\boxed{\displaystyle S_n=\sum_{k=1}^n \left\lfloor\frac{k+1}{2}\right\rfloor {n+1\choose k+1}=n.2^{n-1}}
Ta chứng minh (1) bằng quy nạp theo k.
Ta có:
f(1,n)=1+2+...+n=\frac{n(n+1)}{2}=\left\lfloor\frac{1+1}{2}\right\rfloor {n+1\choose 1+1}Như vậy (1) đúng với k=1
Giả sử (1) đúng đến k-1 thỏa 1\le k-1<n, ta chứng minh (1) cũng đúng với k.
Xây dựng phép đếm f(k,n) theo các tập con có phần tử lớn nhất là j với k\le j\le n
Do j là số lớn nhất nên có {j-1\choose k-1} tập con k phần tử bắt đầu bởi j. Bớt đi số hạng j trong các tập con k phần tử, ta được các tập con k-1 phần tử với phần tử lớn nhất là j-1
Như vậy ta có: \begin{align*}f(k,n)&=\sum_{j=k}^n \left(j{j-1\choose k-1}-f(k-1,j-1)\right)\\&=\sum_{j=k}^n \left(k{j\choose k}-\left\lfloor\frac{k}{2} \right\rfloor{j\choose k}\right)\quad\\&=\left(k-\left\lfloor\frac{k}{2} \right\rfloor\right)\sum_{j=k}^n {j\choose k}\\&=\left\lfloor\frac{k+1}{2}\right\rfloor \sum_{j=k}^n \left[{j+1\choose k+1}-{j\choose k+1}\right]\quad\\&=\left\lfloor\frac{k+1}{2}\right\rfloor{n+1\choose k+1}\end{align*}Như vậy, (1) được chứng minh
Bây giờ, ta sẽ chứng minh:
\boxed{\displaystyle S_n=\sum_{k=1}^n \left\lfloor\frac{k+1}{2}\right\rfloor {n+1\choose k+1}=n.2^{n-1}}
Ta có:
\begin{align*}S_n&=\sum_{k=1}^n \left\lfloor\frac{k+1}{2}\right\rfloor {n+1\choose k+1}&\\&=\sum_{k=1}^n \left\lfloor\frac{k+1}{2}\right\rfloor\left[{n\choose k}+{n\choose k+1}\right]\\&=\sum_{k=1}^n \left\lfloor\frac{k+1}{2}\right\rfloor{n\choose k+1}+\sum_{k=1}^n\left(k-\left\lfloor\frac{k}{2}\right\rfloor\right){n\choose k}\\&=S_{n-1}+\sum_{k=1}^n k{n\choose k-1}-\sum_{k=1}^n\left\lfloor\frac{k}{2}\right\rfloor{n\choose k}&\\&=S_{n-1}+n\sum_{k=1}^n{n-1\choose k-1}-\sum_{k=0}^{n-1}\left\lfloor\frac{k+1}{2}\right\rfloor{n\choose k+1}\\&=S_{n-1}+n\sum_{k=0}^{n-1}{n-1\choose k}-S_{n-1}\\&=n2^{n-1}&\end{align*} Bài toán được chứng minh.
No comments:
Post a Comment