Giả sử ${{F}_{k}}$ là tập hợp tất cả các bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ trong đó ${{A}_{i}}\left( i=\overline{1,k} \right)$ là một tập con của ${{X}_{n}}=\left\{ 1,2,...,n \right\}$. Biết rằng các tập ${{A}_{1}},{{A}_{2}},...,{{A}_{k}}$có thể trùng nhau. Hãy tính \[{{S}_{n}}=\sum\limits_{\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)\in {{F}_{k}}}{\left| \bigcup\limits_{i=1}^{k}{{{A}_{i}}} \right|}\].
Trong một tài liệu có lời giải sau: (mình chép lại nguyên xi)
Do có ${{2}^{n}}$ tập con của ${{X}_{n}}$ nên có ${{2}^{nk}}$ bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$. Với mỗi bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ của ${{X}_{n-1}}$ ta có thể thêm hoặc không thêm n vào tập ${{A}_{i}}$ để được bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ của ${{X}_{n}}$. Với chú ý rằng số bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ của ${{X}_{n-1}}$ là ${{2}^{\left( n-1 \right)k}}$ và có ${{2}^{k}}-1$ cách thêm n vào bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ của ${{X}_{n-1}}$ thì ta có ${{S}_{n}}={{2}^{k}}{{S}_{n-1}}+\left( {{2}^{k}}-1 \right){{2}^{k\left( n-1 \right)}}$.
Dễ thấy ${{S}_{1}}={{2}^{k}}-1$. Từ đấy bằng quy nạp ta chứng minh được ${{S}_{n}}=n{{.2}^{k\left( n-1 \right)}}\left( {{2}^{k}}-1 \right)$.
Mình không hiểu chỗ bôi đỏ? Các bạn giải thích giúp mình nha.