Solution to Problem 1
(a) It is valid, since it includes the basis step at n = 0 and all subsequent values can be obtained from the given recursive relation.
(b) It is valid. It includes the basis step for all initial values. The recursive step clearly defines how the subsequent values can be obtained.
(c) It is invalid. The basis step does not define f(3), which is necessary here for obtaining f(2).
Copyright By PowCoder代写 加微信 powcoder
(d) It is invalid since the definition conflicts itself at n = 1. The basis step defines f(1) = 1. However, the recursive step says f(1) = 2 · f(0) = 0.
Solution to Problem 2
(a)a1 =2andan+1 =4·(n+1)−2=4n−2+4=an+4foralln≥1.
(b)a1 =0,a2 =2,a3 =0,a4 =2andsoon. Italternatebetween0and2. The
recursive step is an = an−2 for all n ≥ 3.
(c)Weobservethata1 =2,a2 =6,a3 =12
andan =n(n+1)=(n−1+2)n=(n−1)n+2n. Thus,itcanbewrittenasa1 =2andan =an−1+2nforalln≥2.
(d) We observe that a1 = 1
andan =n2 =(n−1+1)2 =(n−1)2+2(n−1)+1=(n−1)2+2n−1. Thusitcanbewrittenasa1 =1andan =an−1+2n−1foralln≥2.
Solution to Problem 3
(a) Odd integers are obtained from other odd integers by adding 2. The set of odd integers S can be defined as follows: 1 ∈ S; and if n ∈ S, then n + 2 ∈ S.
(b) Powers of 3 are obtained from other powers of 3 by multiplying by 3. The set of positive integer powers of 3 S can be defined as follows: 3 ∈ S; and if n ∈ S, then 3n ∈ S.
Solution to Problem 4
Basis step:
(w1λ)R = w1R = λw1R = λRw1R.
Inductive step:
Let w2 = w3x, where x is the last symbol of the string w2 and w3 is a string of length one less than the length of w2.
Then (w1w2)R = (w1w3x)R = x(w1w3)R (recursive definition) = xw3Rw1R (inductive hypothesis)
= (w3x)Rw1R (recursive definition)
= w2Rw1R This completes the proof.
Q#5 Solution
Solution to Problem 6
There are three possible initial cases:
Ifx
In all cases (x ≤ y ∧ min = x) ∨ (x > y ∧ min = y) is true.
Solution to Problem 7
We need to show that if p0 is true before S is executed, then q is true afterwards. We assume that that p0 is true before S is executed. As p0 → p1 is true, p1 is also
true. It is given that p1{S}q is true. Therefore, q is true afterwards. Solution to Problem 8
We assume that the iniitial assertion is true. That is a and d are positive integers. We consider the loop invariant p : (a = dq+r)∧(r ≥ 0) and condition cond : r ≥ d.
Initially, r = a and q = 0, thus, p is true before the loop starts. We need to show that p is still true afterwards.
Intheloop,thenewvalueofrisr′ =r−dandthenewvalueofqisq′ =q+1. Thus,dq′+r′ =d(q+1)+(r−d)=a,asdesired.
The loop continues to subtract d from r until cond becomes false. That is r < d. Still we have r ≥ 0, thus, p is true. This implies that the final assertion is also true.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com