精品文档
习题1.3
1.
a) 证明：用第一归纳法 i) 当n = 1 时，左边 = 1/2 = 右边； ii) 对任意的k ? 1，假设当n = k时命题为真，即
111k ?????1?22?3k?(k?1)k?1因为
1111?????? 1?22?3k?(k?1)(k?1)?(k?2)k1??
(k?1)(k?1)?(k?2)
b) c)
.
k?(k?2)?1(k?1)2(k?1)??
(k?1)?(k?2)(k?1)?(k?2)(k?2) 即当n = k+1时命题也为真。 由i) ii)可知，对于任意n?1均有
111n。 ?????1?22?3n?(n?1)n?1证明：用第一归纳法
i) 当n = 1 时，左边 = 2 = 右边；
ii) 对任意的k ? 1，假设当n = k时命题为真，即 2+22+23+?+2k = 2k+1-2
因为 2+22+23+?+2k+ 2k+1= 2k+1-2+2k+1 =2k+2-2
即当n = k+1时命题也为真。 由i) ii)可知，对于任意n?1均有 2+22+23+?+2n = 2n+1-2。
证明：用第一归纳法
i) 当n = 0 时，左边 = 1 ? 0 = 右边； 当n = 1 时，左边 = 2 ? 2 = 右边；
ii) 对任意的k ? 1，假设当n = k时命题为真，即 2k ? 2k 因为 2k+1= 2?2k ? 2?2k ? 2k+2 =2(k+1) 即当n = k+1时命题也为真。 由i) ii)可知，对于任意n?1均有 2n = 2n。
（因为k ? 1）
精品文档
d) e) f)
证明：用第一归纳法
i) 当n = 1 时，左边 = 3 ，右边 = 3，3|3，所以n=1时命题为真； ii) 对任意的k ? 1，假设当n = k时命题为真，即 3 | k3 +2k 因为 (k+1)3 + 2(k+1) = k3 + 3k2 + 3k +1 + 2k +2 = (k3 + 2k) + 3(k2 + k +1) 由于3 | k3 +2k且3 | 3(k2 + k +1)，因此，3 | (k+1)3 +2(k+1) 即当n = k+1时命题也为真。 由i) ii)可知，对于任意n?1均有 3 | n3 +2n。 证明：用第一归纳法
i) 当n = 1 时，左边 = 6 = 右边 = 3，所以n=1时命题为真； ii) 对任意的k ? 1，假设当n = k时命题为真，即 1?2?3 + 2?3?4 + ? + k(k+1)(k+2) = k(k+1)(k+2)(k+3) / 4 因为 1?2?3 + 2?3?4 + ? + k(k+1)(k+2) + (k+1)(k+2)(k+3) = k(k+1)(k+2)(k+3) / 4+ (k+1)(k+2)(k+3) = (k+1)(k+2)(k+3)(k+4) / 4 即当n = k+1时命题也为真。 由i) ii)可知，对于任意n?1均有 1?2?3 + 2?3?4 + ? + n(n+1)(n+2) = n(n+1)(n+2)(n+3) / 4。
证明：证明分三部分
①三个相邻整数中最小者 ? 0； ②三个相邻整数中最小者 = -1； ③三个相邻整数中最小者 ? -2。
对①用第一归纳法，即证9 | n3 + (n+1) 3 + (n+2) 3 i) 当n = 0 时，9 | 9，所以n = 0时命题为真； ii) 对任意的k ? 0，假设当n = k时命题为真，即 9 | k3 + (k+1) 3 + (k+2) 3 因为 (k+1)3 + (k+2) 3 + (k+3) 3 = k3 + 3k2 + 3k +1 + (k+1) 3 + 3(k+1)2 + 3(k+1) +1 + (k+2) 3 + 3(k+2)2 + 3(k+2) +1 = k3 + (k+1) 3 + (k+2) 3 + 3k2 + 3k +1 + 3(k+1)2 + 3(k+1) +1 + 3(k+2)2 + 3(k+2) +1 = k3 + (k+1) 3 + (k+2) 3 + 9k2 + 27k +27 = k3 + (k+1) 3 + (k+2) 3 + 9(k2 + 3k +3) 由于 9 | k3 + (k+1) 3 + (k+2) 3且9 | 9(k2 + 3k +3) 所以，9 | (k+1)3 + (k+2) 3 + (k+3) 3，即当n = k+1时命题也为真。
由i) ii)可知，对于任意n ? 0均有 9 | n3 + (n+1) 3 + (n+2) 3
对③由于9 | n3 + (n+1) 3 + (n+2) 3，所以，9 | (-n)3 + (-(n+1)) 3 + (-(n+2)) 3。 对②因为9 | 0，所以此时命题也为真。
根据以上证明可知，任意三个相邻整数的立方和能被9整除。
.
精品文档
g)
证明：用第一归纳法
i) 当n = 0 时，112 + 121 = 133，133 | 133，所以n = 0时命题为真； ii) 对任意的k ? 0，假设当n = k时命题为真，即 133 | 11 k+2+122 k+1 因为
11 k+3+122 (k+1)+1 = 11?11 k+2+122?122 k + 1 = 11? (11 k+2+122 k + 1) + 133?122 k + 1 由于 133 | 11 k+2+122 k+1 且 133 | 133?122 k + 1 因此，133 | 11? (11 k+2+122 k + 1) + 133?122 k + 1。 即当n = k+1时命题也为真。 由i) ii)可知，对于任意n?1均有 133 | 11 n+2+122 n+1
3. 证明：用第二归纳法
i) 当n = 1 时，(1?5?11?50)?F1?()，所以n = 1时命题为真； 221?51)，所以n = 2时命题为真； 2当n = 2 时，1?F2?F1?F0?1?(
ii) 对任意的k ? 2，假设当2 ? n ? k时命题均为真，
则由 对于任意n?I+，Fn+1 = Fn + Fn-1 可知
Fk+1 = Fk + Fk-1 ? (
1?5k?11?5k?2)?() 22
? (1?5k?21?51?5k?23?5)(?1) ? ()() 2222
? (1?5k) 21?5k?21?5k?3)?() 22
Fk+1 = Fk + Fk-1 ? (
? (1?5k?31?51?5k?33?5)(?1) ? ()() 2222
? (1?5k?1) 2 即当n = k+1时命题也为真。 由i) ii)可知，对于任意n?1均有
(1?5n?21?5n?1)?Fn?() 。 22.
精品文档
4. 分析：（证明略） 设n = (m+1) q + r，m ? r > 0。
首先，甲扳倒r根，然后每当乙扳倒x（1? x ? m）根，因为1? (m+1) – x ? m，所以此时甲可扳倒(m+1) – x根，故甲总能获胜。 证明：对q（即n除以m+1的商）用第一归纳法。 i) 当q = 0时，因为n = r且m ? r ? 1，所以甲可一次将r根全部扳倒，则甲获胜。 ii) 对任意的k ? 0，假设当q = k时命题为真，
则当q = k+1时，即存在r使得n = (m+1) (q+1) + r，m ? r > 0 ，由于 此时甲可扳倒r根，然后乙只能扳倒x（1? x ? m）根，此时剩下n? = (m+1)q+(m+1)-q根， 因为1? (m+1) – x ? m，则根据归纳假设可知甲总能获胜。 即当q = k+1时命题也为真。
由i) ii)可知，对于任意q ? 0均有甲总能获胜。
5. 证明：用第一归纳法
对于每个i ? i0，用Q(i)表示下列命题： 对于任意j ? j0，P (i, j)皆真。 下面验证：Q(i)满足第一归纳法的条件。 i) Q(i0)为真， 因为（对j用第一归纳法）：
a) P(i0, j0)为真；
b) 若P(i0, j)为真，则P (i0, j+1)为真； 由归纳法可知，Q(i0)为真。 ii) 若Q(i)为真（i ? i0），即对于任意i ? i0，j ? j0，P (i, j)为真。 则对于任意j ? j0，P(i+1, j)为真，即Q (i+1)为真。 由i)和ii)可知，对于任意i ? i0，Q (i)皆真。 所以，对于任意i ? i0，j ? j0，P (i, j)为真。
6. 证明：假设有n ? N使n ? n ，即 {n} ? n ，故n+ = {n}?n ? n ，同时n ? n+ ，所以
n = n+。矛盾！（与皮亚诺公理矛盾）
10. 证明：假设有m ? N使n < m，则由“<”定义可知n ? m，所以由习题7有n ? m。因
为n ? m 且n ? m，所以 n?{n} ? m，即n+ ? m。
而m < n+，则由“<”定义可知m ? n+，由习题7有m ? n+。
n+ ? m与m ? n+矛盾，所以假设不成立，即不可能有m ? N使n < m < n+。
.
精品文档
习题1.4
1.
a) A ? {1} ? B = {<0, 1, 1>, <0, 1, 2>, <1, 1, 1>, <1, 1, 2> }
b) A2 ? B = {<0, 0, 1>, <0, 0, 2>, <0, 1, 1>, <0, 1, 2>, <1, 0, 1>, <1, 0, 2>, <1, 1, 1>, <1, 1, 2> } c) (B ? A)2 = { <1, 0, 1, 0>, <1, 0, 1, 1>, <1, 0, 2, 0>, <1, 0, 2, 1>,
<1, 1, 1, 0>, <1, 1, 1, 1>, <1, 1, 2, 0>, <1, 1, 2, 1>, <2, 0, 1, 0>, <2, 0, 1, 1>, <2, 0, 2, 0>, <2, 0, 2, 1>, <2, 1, 1, 0>, <2, 1, 1, 1>, <2, 1, 2, 0>, <2, 1, 2, 1> }
2. 题号 是否正确 a) ? （反例：A=D={a}，B=C=?，则左边={
d) ? （反例：A=C={1, 2}，B={1}，D={2}，则左边={<2, 1>}，
而右边={<1, 1>, <2, 1>, <2, 2>}）
7. 证明：题目等价于证明：若
② {a, A} = {d, B}且{b, B} = {c, A} 则因为A?B，所以a = B, d = A, b = A且c = B。
所以，a = c且b = d。
故总有：a = c且b = d。
第二章 二元关系
习题2.1
1. d) e) 2.
R = {<0, 0>, <0, 2>, <2, 0>, <2, 2>} R = {<1, 1>, <4, 2>}
R1 ? R2 = {<1, 2>, <2, 4>, <3, 3>, <1, 3>, <4, 2>} R1 ? R2 = {<2, 4>}
.
国防科大版离散数学习题答案
