当n是偶数时，最后一次会出现F0=0项
当n是奇数时，最后一次会出现F1=1项
4）证明 用2）的结论
下面证明是最大公约数
设F(n,m)不是最大公约数， FN是,
则 m|N, n|N 则 N=<(n,m)与 N>(n,m)矛盾 是最大公约数
29. 从1到n的自然数中选取k个不同且不相邻的数，设此选取的方案为f(n,k)。
（a）求f(n,k)的递推关系。 （b）用归纳法求f(n,k)。
（c）若设1与n算是相邻的数，并设在此假定下从1到n的自然数中选取k个不同且不相邻的k个数的方案数为g(n,k)，利用f(n,k)求g(n,k)。 解：...
（a）
（b）
（c）
30. 设S2(n,k)是第二类Stirling数。 证明
证明：...
设与第n+1号球同盒的球有n-k个，这样，其他k个球就放入另外m-1个盒子， k=m-1,m,…,n。 即从n个不同的球中取k个放入m-1个相同的盒子的方案有
31. 求下图中从A点出发到n点的路径数。
解：...
把上方的点序列设为an
把下方的点序列设为bn 可得第推关系
特征方程为 解得
代入初值可解
32. n位0,1符号串，求从左向右只在最后两位才出现0，0的符号串的数目。 解：...
设所求的串的个数为an，相邻不同为0的串的个数为bn
特征方程为 解得
代入初值可解
33. 试证
证明：...
用数学归纳法
I n=2时
成立
II 设n=k时成立即
当n=k+1时
由I、II知题设成立
1.某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议
解: 设Ai为甲与第i个朋友相遇的会议 集，i＝1，?，6．则
故甲参加的会议数为:28+5=33.
2.求从1到500的整数中被3和5整除但不被7整除的数的个数. 解: 设A3：被3整除的数的集合 A5：被5整除的数的集合 A7：被7整除的数的集合
所以
3. n个代表参加会议，试证其中至少有2人各自的朋友数相等。
解:每个人的朋友数只能取0，1，?，n－1．但若有人的朋友数为0，即此人和其 他人都不认识，则其他人的最大取数不超过n－2．故这n个人的朋友数的实际取数只 有n－1种可
能．，所以至少有２人的朋友数相等．
4. 试给出下列等式的组合意义.
解: