集与偶子集个数相等，故均为个．
（2）设an(bn)表示Sn中全体奇（偶）子集容量之和． 若n(≥3)是奇数，则Sn的奇子集由如下两类：（1）Sn－1的奇子集；（2）Sn－1的偶子集与集{n}的并，于是得
an=an－1＋（bn－1＋n·2n－2），①
又Sn的偶子集可由Sn－1的偶子集和Sn－1的奇子集与{n}的并构成，所以 bn = bn－1＋（an－1＋n·2n－2），② 由①，②，便得an= bn．
若n（≥4）是偶数，同上可知 an=an－1＋（an－1＋n·2n－2）， bn = bn－1＋（bn－1＋n·2n－2），
由于n－1是奇数，由上面已证an－1= bn－1，从而an = bn． 综上即知，an = bn，n=3，4?
（3）由于Sn的每一个元素均在2n－1个Sn的子集中出现，所以，Sn的所有子集容量之和为2n－1（1＋2＋?＋n）=2n－2n（n＋1)． 又由（2）知，an=bn，所以
说明（2）的证明中，建立了递推关系．这也是解决“计数”问题的一个有效方法．
例4、设A是集合S={1，2，…1000000}的一个恰有101个元素的子集．证明：在S中存在数t1，t2，…t100，使得集合
际数学奥林匹克试题）
[分析及答案]
证明：考虑集合D={x－y|x，y∈A},则
若
，设
，则a=x＋ti，a=y＋tj，其中x，y∈A，则ti－tj=y－x∈D．
中，每两个的交集为空集．（2003年国
若ti－tj∈D，即存在x，y∈A，使得ti－tj=y－x，从而x＋ti= y＋tj，即所以，
的充要条件是ti－tj∈D．于是，我们只需在集合S中取出100个元素，使得
其中任意两个差都不属于D．
下面用递推方法来取出这100个元素．
先在S中任取一个元素t1，再从S中取一个t2，使得
这是因为取定t1
后，至多有10101个S中的元素不能作为t2，从而在S中存在这样的t2．若已有k(≤99)个S中的元素t1，t2，?，tk满足要求，再取tk＋1，使得t1，?，tk都不属于tk＋1＋D={ tk＋1＋x|x∈D}，这是因为t1，t2，?，tk取定后，至多有10101k≤999999个S中的数不能作为tk＋1，故在S中存在满足条件tk＋1．所以，在S中存在t1，t2，?，t100，其中任意两个的差都不属于D．
综上所术，命题得证．
说明：条件|S|=106可以改小一些．一般地，我们有如下更强的结论： 若A是S={1,2,?，n}的k元子集，m为正整数，满足条件n>(m－1)t1，?，tm，使Aj={x＋tj|x∈A}，j=1,?m中任意两个的交集为空集．
例5、求函数解答：由题设可得x2－3x＋2=y2－2xy＋x2， 即（2y－3）x=y2－2．
的值域．（2001年全国高中数学联赛试题）
，所以
则存在S中的元素
由上式知由
故x0≤1，于是
综上，所求的函数的值域为
说明：我们先求出了y的范围，这是不是函数的值域呢？第二部分说明了对于
中的任意一个数y0，总存在一个x0，使得，这就证明了
函数的值域是