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.