HW 6 Answer Key

Section 3.2

55. Let P (n) be the statement that if x_{1}, x_{2}, · · x_{n} are n distinct real numbers, n-1 multiplications are required to form their product.The basis case P (1) is true since 1 − 1 = 0 multiplications are required to find the product of x_{1}, as there is only one factor. Suppose that P (k) is true for 1 ≤ k ≤ n. The last multiplication used to to find the product of n + 1 terms, is a multiplication of the product of the first k of these numbers for some k and the product of the last n + 1 − k of them. By the inductive hypothesis, k − 1 multiplications are used to find the product of the k of the numbers, and n − k multiplications are used to find the product of n + 1 − k of them. Since one more multiplication is used to find the productof all of them the total no. of multiplications used equals (k − 1) + (n − k) + 1 = n. Hence P (n + 1) is true.

Section 3.3

4a.f(2) = f(1) − f(0) = 1 − 1 = 0 f(3) = f(2) − f(1) = 0 − 1 = −1 f(4) = f(3) − f(2) = −1 − 0 = −1 f(5) = f(4) − f(3) = −1 + 1 = 0 b. Clearly f(n) = 1 for all n, since 1 · 1 = 1. c. f(2) = f(1)^{2} + f(0)^{3} = 1^{2} + 1^{3} = 2 f(3) = f(2)^{2} + f(1)^{3} = 2^{2} + 1^{3} = 5 f(4) = f(3)^{2} + f(2)^{3} = 5^{2} + 2^{3} = 33 f(5) = f(4)^{2} + f(3)^{3} = 33^{2} + 5^{3} = 1214 d. Clearly f(n) = 1 for all n, since 1/1 = 1.

6 Many answers are possible 6a. Each term is 4 more than that term before it. We can therefore define the sequence by a_{1} = 2 and a_{n+1} = a_{n} + 4 6b. We note that the terms alternate: 0,2,0,2, and so on. Thus we could define the sequence by a_{1} = 0, a_{2} = 2, and a_{n} = a_{n−2} for all n ≥ 3 6c. The sequence starts out 2, 6, 12, 20, 39, and so on. The differences between successive terms are 4, 6, 8, 10, and so on. Thus the n^{th} term is 2n greater that the term preceding it; In symbols: a_{n} = a_{n−1} +2n. Together with the initial condition of a_{1} = 2. 6d. The sequence starts out 1, 4, 9, 16, 25, and so on. The differences between successive terms are 3, 5, 7, 9, and so on - the odd numbers. The n^{th} term is 2n-1 greater than the term precedint it; In symbols: a_{n} = a_{n−1} + 2n − 1. Together with the initial condition a_{1} = 1, this defines the sequence recursively.

10 The base case for n = 1 is clear since f_{1}^{2} = f_{1}f_{2} = 1.

Assume the inductive hypothesis. Then f_{1}^{2} + f_{2}^{2} + ⋯f_{n}^{2} + f_{n+2}^{2} = f_{n}f_{n+1} + f_{n+1}^{2} = f_{n+1}(f_{n} + f_{n+1}) = f_{n+1}f_{n+2} as desired.

12 The base case for n = 1 is clear since f_{2}f_{0} − f_{1}^{2} = 1 · 0 − 1^{2} = −1 = (−1)^{1}.

Assume the inductive hypothesis. Then f_{n+2}f_{n} − f_{n+1}^{2} = (f_{n+1} + f_{n})f_{n} − f_{n+1}^{2} = f_{n+1}f_{n} + f_{n}^{2} − f_{n+1}^{2} = −f_{n+1}(f_{n+1} − f_{n}) + f_{n}^{2} = −(f_{n+1}f_{n−1} − f_{n}^{2}) = −(−1)^{n} = (−1)^{n+1}.

22 a. Odd integers are obtained from other odd integers by adding 2.

We can define this set S 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. We can define this set S as follows: 3 ∈ S (this is 3^{1}); and if n ∈ S, then 3n ∈ S. c. There are several ways to do this. We will assume that the variable for these polynomials is the letter x. All integers are in S (this base case gives us all the constant polynomials); if p(x) ∈ S and n is any integer, then xp(x) + n is in S. Another method constructs the polynomials term by term. Its base case is to let 0 be in S; and its inductive step is to say that p(x) ∈ S, c is an integer, and n is a nonnegative integer, the p(x) + c(x)^{n} is in S.

29. w^{0} = λ and w^{n+1} = ww^{n} where w^{i} represents the concatenation of i copies of w.

32.There can be several different correct answers for this one.

The base case would be that 0 belongs to the set. The key fact in the recursive case is that any string containing more 0’s than 1’s could be a concatenation of these strings, or a concatenation with a 1 before, in between or after them. If x and y are in the set then so are xy, x1y, xy1, 1xy.

33. Let P(i) be ”l(w^{i}) = i.l(w).”

P (0) is true since l(w^{0}) = 0 = 0.l(w). Assume P(i) is true. Then l(w^{i+1}) = l(ww^{i}) = l(w) + l(w^{i}) = l(w) + i.l(w) = (i + 1).l(w) which gives the required proof.

36a. A(1, 0) = 0 by the second line of the definition.

b. A(0, 1) = 2 by the first line of the definition. c. A(1, 1) = 2 by the third line of the definition. d. A(2, 2) = A(1, A(2, 1)) = A(1, 2) = A(0, A(1, 1)) = A(0, 2) = 4