Free Essay

Submitted By AnnAnnAngel

Words 444

Pages 2

Words 444

Pages 2

Worksheet 9 answers

Tuesday 13 October 2015

Practice using mathematical induction

1. (3.1 #10) When n = 1, we have 1 · 1! = 2! − 1. Suppose that the statement is true for n = k: k i(i!) = (k + 1)! − 1. i=1 For n = k + 1, we have k+1 k

i(i!) = i=1 i(i!)+(k+1)(k+1)! = (k+1)!−1+(k+1)(k+1)! = (k+1)!(k+1+1)−1 = ((k+1)+1)!−1. i=1 Thus, by induction, the statement is true for all n.

2. (3.1 #19) Claim: 5 + 9 + 13 + · · · + (4n + 1) = n(2n + 3), for all n. When n = 1, we have 5 = 1(2 · 1 + 3).

Suppose that the statement is true for n = k: 5+9+13+· · ·+(4k +1) = k(2k +3). Then, for n = k +1, we have 5+9+13+· · ·+(4k+1)+(4(k+1)+1) = k(2k+3)+4k+5 = 2k 2 +7k+5 = (k+1)(2(k+1)+3).

Thus, by induction, the statement is true for all n.

Note: You might ask, “How did you come up with the formula n(2n + 3) in the ﬁrst place?” When n = 1, the sum is 5, when n = 2, the sum is 14, and when n = 3, the sum is 27. Given other sum formulas, it is reasonable to hypothesize that the formula will be a quadratic function of n; that is, of the form an2 + bn + c. The ﬁrst three sums give us a system of three equations in three variables: a + b + c = 5, 4a + 2b + c = 14, and 9a + 3b + c = 27. It is not hard to solve: a = 2, b = 3, c = 0. The resulting quadratic, 2n2 + 3n, produces the ﬁrst few sums correctly, so we then pursue a proof that it is correct for all n.

Alternately: assuming the formula

2n(n + 1) + n = 2n2 + 3n.

n i=1 i = n(n + 1)/2, write

n i=1 (4i

+ 1) = n + 4

i (why?) =

3. (3.1 #22) When n = 1, we have cos x + i sin x = cos x + i sin x. Suppose that the statement is true for n = k: (cos x + i sin x)k = cos(kx) + i sin(kx). For n = k + 1, we have (cos x + i sin x)k+1 =

(cos x + i sin x)k (cos x + i sin x) = (cos(kx) + i sin(kx))(cos x + i sin x) = cos(kx) cos x − sin(kx) sin x + i(cos(kx) sin x + sin(kx) cos x) = cos((k + 1)x) + i sin((k + 1)x). Thus, by induction, the statement is true for all n.…...