Solution to Problem 1
Basis step:
P (1) is true since 1 · 1! = 2! − 1
Inductive step:
Copyright By PowCoder代写 加微信 powcoder
We assume that P (k) is true. Now we need to show that P (k + 1) is also true. 1 · 1! + 2 · 2! + … + k · k! + (k + 1) · (k + 1)! = (k + 1)! − 1 + (k + 1) · (k + 1)!
Thus, P (k + 1) is also true.
Solution to Problem 2
Basis step:
Forn=7,37 =2187and7!=5040.
P(7) is true since 37 < 7!.
Inductive step:
We assume that P (k) is true, so 3k < k!.
Hence,3k+1 =3·3k <(k+1)·3k <(k+1)·k!<(k+1)!. It is clear that P (k + 1) is also true.
= (k + 1)!(k + 2) − 1 = (k + 2)! − 1
Solution to Problem 3
Basis step:
P (1) is true since 6 | (13 − 1).
Inductive step:
We assume that P (k) is true, that is 6 | (k3 − k).
(k+1)3 −(k+1)=(k3 −k)+3k(k+1).
As k(k + 1) is always even, 3k(k + 1) is an even multiple of 3, that means 3k(k + 1) is divisible by 6. We already got 6 | (k3 − k) as the inductive hypothesis.
Thus, P (k + 1) is also true.
Solution to Problem 4
Basis step:
P(1) is true since 21 | (42 + 51).
Inductive step:
We assume P (k) is true, that means 21 | (4k+1 + 52k−1). 4k+1+1 +52(k+1)−1 = 4k+2 +52k+1 = 4·4k+1 +5·52k
Therefore, P (k + 1) is also true.
=4·(4k+1 +52k−1)+5·52k −4·52k−1 =4·(4k+1 +52k−1)+21·52k−1
Solution to Problem 5
Basis step:
P(1) is true since 1 = 20. Subsequent steps:
P(2) is true since 2 = 21
P (3) is true since 3 = 21 + 20 P(4) is true since 4 = 22
Inductive step:
We assume that P(j) is true for 1 ≤ j ≤ k. It means that every positive integer
up to k can be written as a sum of distinct powers of 2.
We need to show that k + 1 can be written as a sum of distinct powers of 2. There
are two possible cases:
If k + 1 is odd, then k is even. According to the inductive hypothesis, k can be written as a sum of distinct powers of 2. Clearly, k + 1 can also be written as a sum of distinct powers of 2 since 1 = 20.
If k + 1 is even, then (k + 1)/2 is a positive integer and (k + 1)/2 ≤ k. According to the inductive hypothesis, (k + 1)/2 can be written as a sum of distinct powers of 2. Thus, k + 1 can be written by increasing those powers by 1. This completes the proof.
Solution to Problem 6
We will apply the principle of strong induction.
The basis step is n = b. It is given that P(b) is true.
For the inductive step, k ≥ b, we assume that P(j) is true for b ≤ j ≤ k. Now we need to prove that P (k + 1) is true. There are two possible cases:
If k + 1 ≤ b + j, then P(k + 1) is true by the given conditions.
If k + 1 > b + j, then P(k + 1) is true by the given conditional statement and the
inductive hypothesis. This completes the proof.
Solution to Problem 7
The flaw is located in the inductive step. It implicitly assumes that k ≥ 1 to intro- duce the denominator.
The inductive step is not justified since the basis step was n = 0. For n = 1, it gives a = 1. The inductive hypothesis is not valid for other nonzero values of a.
Solution to Problem 8
The basis step is n = 1. We get f2f0 − f12 = 1 · 0 − 12 = (−1)1. The inductive hypothesis gives that fn+1fn−1 − fn2 = (−1)n.
fn+2fn − fn2+1 = (fn+1 + fn)fn − fn2+1 = fn+1fn + fn2 − fn2+1
= −fn2+1 + fn+1fn + fn2 = −fn+1(fn+1 − fn) + fn2 = −(fn+1fn−1 − fn2)
This completes the proof.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com