Question

一个非空集合中的各个元素之和是3的倍数，则称该集合为“好集”．

记集合 {1，2，3，…，3n}的子集中所有“好集”的个数为f(n)．

（1）求f(1)，f(2)的值；

（2）求f(n)的表达式．

Answer 1

 (1)易得f(1)=3；     

当n=2时，集合{1，2，3，4，5，6}的子集中是“好集”的有：

单元集：{3}，{6}共2个，双元集{1,2}，{1,5}，{2,4}，{4,5}，{3,6}共5个，三元集有：{1,2,3}，{1,2,6}，{1,3,5}，{1,5,6}，{4,2,3}，{4,2,6}，{4,3,5}，{4,5,6}共8个，四元集有{3,4,5,6}，{2,3,4,6}，{1,3,5,6}，{1,2,3,6}，{1,2,4 ,5}共五个，五元集{1,2,4,5,6}，{1,2,3,4,5}共2个，还有一个全集．

故f(2)＝1+(2+5)×2+8＝23．       

  (2)首先考虑f(n+1)与f(n)的关系．

集合{1，2，3，…，3n，3n+1，3n+2，3n+3}在集合{1，2，3，…，3n}中加入3个元素3n+1，3n+2，3n+3．故f(n+1)的组成有以下几部分：①原还的f(n)个集合；②含有元素3n+1的“好集”是{1，2，3，…，3n}中各元素之和被3除余2的集合，含有元素是3n+2的“好集”是{1，2，3，…，3n}中各元素之和被3除余1的集合，含有元素是3n+,3的“好集”是{1，2，3，…，3n}中各元素之和被3除余0的集合，合计是2³ⁿ；③含有元素是3n+1与3n+2的“好集”是{1，2，3，…，3n}中各元素之和被3除余0的集合，含有元素是3n+2与3n+3的“好集”是{1，2，3，…，3n}中各元素之和被3除余1的集合，含有元素是3n+1与3n+3的“好集”是{1，2，3，…，3n}中各元素之和被3除余2的集合，合计是2³ⁿ；④含有元素是3n+1，3n+2，3n+3的“好集”是{1，2，3，…，3n}中“好集”与它的并，再加上{3n+1，3n+2，3n+3}。

   所以，f(n+1)＝2 f(n)+2×2³ⁿ+1．         

   两边同除以2ⁿ⁺¹，得－＝4ⁿ+，

  所以  ＝4^n-1+4^n-2+…+4+++…++＝+1－，

 即f(n)＝+2ⁿ－1．