Gọi A là tập tất cả các tập con m- tách được gồm $k$ phần tử của X và B là tập tất cả các tập con gồm k phần tử của tập $Y=\{1,2,…, n-(k-1)(m-1) \}$.

Ta xây dựng song ánh từ A đến B như sau: Với $S=\{s_1,s_2,…,s_k \} \in A$ ($s_1<s_2<…<s_k$) lấy tương ứng $f(S)=\{s_1, s_2-(m-1), s_3-2(m-1),…, s_k-(k-1)(m-1) \}$. Dễ chứng minh đây là một song ánh. Từ đó có $C^k_{n-(k-1)(m-1)}$ tập thoả yêu cầu đề bài.

Gọi B là tập tất cả các tập con không chứa phần tử n của X và C là tập tất cả các tập con có chứa phần tử n của X.

Ta xây dựng song ánh từ B đến C như sau: Với $S=\{s_1,s_2,…,s_k \} \in B$ ($s_1<s_2<…<s_k<n$) lấy tương ứng $f(S)=\{s_1,s_2,…,s_k,n \} ,$ nhận thấy $f(S)\in C$. Dễ chứng minh đây là một song ánh.

Ta có: $|B|=|C|=2^{n-1};B\cup C= \emptyset;B\cap C=X$

Và $m(S)+m(f(S))=n$

Do đó: $$\sum \limits_{A_i \subset X} m(A_i) =\sum \limits_{B_i \subset B} m(B_i) +\sum \limits_{C_i \subset C} m(C_i)=n\cdot 2^{n-1}$$

Gọi A là họ các tập béo thỏa yêu cầu đề bài, B là họ các các tập con của X có tính chất hai phần tử bất kỳ hơn kém nhau 3 đơn vị. Ta thiết lập một ánh xạ $f$ đi từ A đến B như sau: giả sử $x=\{a_1,a_2,…,a_k\} \in A$, ta có thể giả sử $k \le a_1<a_2<a_3<…<a_k \le n$. Đặt $b_1=a_1-k+1, b_2=a_2-k+2,…,b_k=a_k$. Khi đó $$ a_{i+1} \ge a_i+2, i=1,2,…,k-1. $$

Suy ra $a_{i+1}-a_i \ge 2$ do đó $b_{i+1}-b_i \ge 3$ và $b_1 \ge 1, b_k \le n.$ Định nghĩa $f(x)=y=\{b_1,b_2,…,b_k\}$, suy ra $y \in B$. Vậy $f$ là một ánh xạ, hơn nữa dễ thấy $f$ là một song ánh do đó ta có điều cần chứng minh.

$(x_1,x_2,…,x_{n-1},x_n) \in S$ mà $x_n \ne n$ ta cho tương ứng với bộ $(x_1+1,x_2+2,…,x_{n-1}+1,x_n+1)$, với $(x_1,x_2,…,x_{n-1},n) \in S$ ta cho tương ứng với bộ $(0,x_1,…,x_{n-1}).$ \

Dễ chứng minh $f$ là một song ánh, $f$ hoán vị S và $f(S)=S.$ Vì tổng tất cả các phần tử của các bộ trong S và $f(S)$ là như nhau trong khi tương ứng thứ nhất tăng tăng tổng này lên $n$ đơn vị, tương ứng thứ hai giảm tổng này đi $n$ đơn vị nên số lần xuất hiện của hai tương ứng này là như nhau. Từ đó suy ra điều cần chứng minh

Gọi $A_n, B_n$ lần lượt là tập các xâu nhị phân độ dài $n$ thỏa điều kiện thứ nhất và thứ hai. Với mỗi xâu nhị phân $(x_1,x_2,…,x_n)$ ta cho tương ứng với một xâu nhị phân $(y_0,y_1,…,y_n)$ xác định bởi $y_0=0$ và $$ y_i=x_1+x_2+…+x_i \ mod \ 2, i=1,2,…,n. \ \ \ (*)$$

Khi đó $$ x_i=y_i+y_{i-1} \ mod \ 2, i=1,2,…,n. $$

Dễ thấy (*) là một song ánh giữa tập tất cả các xâu nhị phân độ dài $n$ và tập tất cả các xâu nhị phân độ dài $n+1$ trong đó có bit đầu tiên là 0. Hơn nữa xâu nhị phân $(x_1,x_2,…,x_n)$ có 3 bit 0,1,0 liên tiếp theo thứ tự này khi và chỉ khi xâu nhị phân tương ứng $(y_0,y_1,…,y_n)$ có 4 bit liên tiếp theo thứ tự là 0,0,1,1 hoặc 1,1,0,0. Nói cách khác một xâu nhị phân thuộc $A_n$ sẽ tương ứng với một xâu nhị phân thuộc $B_{n+1}$ và bắt đầu bằng bit 0. Vì số xâu nhị phân thuộc vào $B_{n+1}$ bắt đầu bằng bit 0 đúng bằng một nửa số xâu nhị phân thuộc vào $B_{n+1}$ do đó ta có $b_{n+1}=2a_n$ (điều phải chứng minh).