HW 5 Answer Key

Section 3.2

4. Base case: n = 0 2 = \frac{1−(−7)}{4} is true. We assume that

2 − 2.7 + 2.7^{2} − 2.7^{3}...2.(−7)^{n} = \frac{1 − (−7)^{n+1}}{4} .

We want to show that

2 − 2.7 + 2.7^{2} − 2.7^{3}...2.(−7)^{n+1} = \frac{1 − (−7)^{n+1+1}}{4} .

Using the inductive hypothesis we are able to re-write the left side of the equation

\frac{1 − (−7)^{n+1}}{4} + 2.(−7)^{n+1}

= \frac{1 − (−7)^{n+1} + 8.(−7)^{n+1}}{4}

= \frac{1 + 7.(−7)^{n+1}}{4}

= \frac{1 − (−7).(−7)^{n+1}}{4}

= \frac{1 − (−7)^{n+1+1}}{4}

QED

6 By looking at the first few sums, we guess that the sum is n/n + 1 Prove this by induction.

Base case: n = 1

\frac{1}{1 + 1} = \frac{1}{2}

We assume that

\frac{1}{1 ∗ 2} + \frac{1}{2 ∗ 3} + ... + \frac{1}{n(n + 1)} = \frac{n}{n + 1}

We want to show that

\frac{1}{1 ∗ 2} + \frac{1}{2 ∗ 3} + ... + \frac{1}{n(n + 1)} + \frac{1}{(n + 1)(n + 2)} = \frac{n + 1}{n + 2}

Using the inductive hypothesis we are able to re-write the left side of the equation

\frac{n}{n + 1} + \frac{1}{(n + 1)(n + 2)} = \frac{n^{2} + 2n + 1}{(n + 1)(n + 2)} = \frac{n + 1}{n + 2}

QED

8. Inductive Hypothesis:

∑_{1}^{n} j^{3} = [n(n + 1)/2]^{2} whenever n is a positive integer Base case:

n = 1

∑_{1}^{1} j^{3} = 1^{3} = 1

[1(1 + 1)/2]^{2} = 1^{2} = 1

1 = 1

Inductive Step:

∑_{1}^{n+1} j^{3} = [(n + 1)(n + 2)/2]^{2}

∑_{1}^{n+1} j^{3} = [(n + 1)(n + 2)/2]^{2}  What you’re trying to prove
∑_{1}^{n+1} j^{3} = ∑_{1}^{n} j^{3} + (n + 1)^{3}  math
= [(n + 1)(n + 2)/2]^{2} + (n + 1)^{3} Inductive hypothesis
= (n + 1)^{2}(n^{2}/4 + n + 1)  math
= (n + 1)^{2}((n^{2} + 4n + 4)/4)  math
= ((n + 1)(n + 2)/2)^{2}  math

QED

10 The base case is clear, since 1 · 1! = 2! − 1 Assuming the inductive hypotheses, we have 1 · 1! + 2 · 2! + ⋯ + n · n! + (n + 1) · (n + 1)! = (n + 1)! − 1 + (n + 1) · (n + 1)! = (n + 1)!(1 + n + 1) − 1 = (n + 2)! − 1 QED

11. Let P(n) be 1 + nh ≤ (1 + h)^{n}, h ≥ 0. Basis Step: It is true for n = 0, 1 + 0.h = 1 ≤ 1 = (1 + h)^{0}. Inductive Step: Assume 1 + nh ≤ (1 + h)^{n}.Then since (1 + h) ≥ 0, (1 + h)^{n+1} ≥ (1 + h)(1 + h)^{n} ≥ (1 + h)(1 + nh) = 1 + (n + 1)h + nh^{2} ≥ 1 + (n + 1)h.

14. Base case is n = 2.2! < 2^{2}.

Inductive Step: (n + 1)! < (n + 1)^{n+1}

(n+1)!  = (n+1)n!  math (n+1)n!  < (n + 1)n^{n}  Inductive Hypothesis (n + 1)n^{n}  < (n + 1)(n + 1)^{n} math (n + 1)(n + 1)^{n} = (n + 1)^{n+1}  math QED

15 This problem basically asks you to prove

∑_{1}^{n} j · (j + 1) = \frac{n(n+1)(n+2)}{3} Base Case n = 1 :

1 · (1 + 1) = 1 · 2 = 2 \frac{1(1+1)(1+2)}{3} = \frac{1·2·3}{3} = \frac{6}{3} = 2 2 = 2 QED

Assuming the inductive hypothesis prove: ∑_{1}^{n+1} j · (j + 1) = \frac{(n+1)(n+2)(n+3)}{3}

∑_{1}^{n+1} j · (j + 1)

= ∑_{1}^{n} j · (j + 1) + (n + 1)(n + 2)

= \frac{n(n+1)(n+2)}{3} + (n + 1)(n + 2) = \frac{n(n+1)(n+2)}{3} + \frac{3(n+1)(n+2)}{3} = \frac{(3+n)(n+1)(n+2)}{3} = \frac{(n+1)(n+2)(n+3)}{3} QED 18. The base case, n = 2, is the true statement that 5/4 is less than 6/4. Assume the inductive hypothesis.

Then we have 1 + \frac{1}{4} + \frac{1}{9} + ... + \frac{1}{n^{2}} ≤ 2 − \frac{1}{n} 1 + \frac{1}{4} + \frac{1}{9} + ... + \frac{1}{n^{2}} + \frac{1}{n+1^{2}} ≤ 2 − \frac{1}{n} + \frac{1}{(n+1)^{2}} = 2 − (\frac{1}{n} − \frac{1}{n+1^{2}} ) = 2 − (\frac{n^{2}+2n+1−n}{n.(n+1)^{2}})

= 2 − \frac{n^{2}+n}{n.(n+1)^{2}} − \frac{1}{n.(n+1)^{2}} = 2 − \frac{1}{n+1} − \frac{1}{n.(n+1)^{2}} ≤ 2 − \frac{1}{n+1}

22.The statement is true for the base case, n = 0, since 6|0 . Suppose that 6|(n^{3} − n). We must show that 6|((n + 1)^{3} − (n + 1)) .If we expand the expression in question, we get n^{3} + 3n^{2} + 3n + 1 − n − 1 = (n^{3} − n) + 3n(n + 1) . By the inductive hypothesis 6 divides the first term. Furthermore clearly 3 divides the second term, and the second ternm is also even, since one of n and n+1 is even. Therefore 6 divides the second term as well. This tells us that 6 divides the given expression as desired.

36.We prove this by induction on k. The base case k = 0, is the trivial statement that 1 ≡ 1(modm). Suppose that the statement is true for k. We must show it for k + 1. so let a ≡ b(modm). By the inductive hypothesis we know that a^{k} ≡ b^{k}(modm). Then we apply theorem 7 from section 2.3 to conclude that a.a^{k} ≡ b.b^{k}(modm), which by definition says that a^{k+1} ≡ b^{k+1}(modm), as desired. This could also be done in other ways without using theorem by multiplying by a and b respectively and simplifying.

40. The base case is trivial since it merely says ¬p_{1} is equivalent to itself. Assuming the inductive hypothesis, we look at ¬(p_{1}∨p_{2}∨.....∨p_{n}∨p_{n+1}) . By DeMorgan’s law (grouping all but the last term together) this is the same ¬(p_{1} ∨p_{2}...∨p_{n})∧¬p_{n+1} .But, by the inductive hypothesis, this equals, ¬p_{1} ∧¬p_{2}...¬p_{n} ∧¬p_{n+1} , as desired.

43 The implication P (1) → P (2) is false.

The two sets do not overlap if n + 1 = 2 .

44 The flaw comes in the inductive step, where we are implicitly assuming that n ≥ 1 in order to talk about a^{n−1} in the denominator (otherwise the exponent is not a nonnegative integer, so we cannot apply the inductive hypothesis). We checked the base case only for n = 0, so we are not justified in assuming that n ≥ 1 when we try to prove the statment for n + 1 in the inductive step. Indeed it is precisely at n = 1 that the proposition breaks down.

46 Suppose that the statment ∀nP (n) has been proved by this method. Let S be the set of counterexamples to P, i.e. let S = {n|¬P (n)}. We will show that S = ϕ. If S ≠ ϕ, then let n be the minimum element of S (which exists by the well-ordering property). Clearly n ≠ 1 and n ≠ 2, by the base cases of our proof method. But since n is the least element of S and n ≥ 3, we know that P (n − 1) and P (n − 2) are true. Therefore by the inductive step of our proof method, we know that P(n) is also true. This contradicts the choice of n. Therefore S = ϕ, as desired.

Base case: n = 1 ∑_{1}^{1} 1/j(j + 1) = 1/1 · 2 = 1/2 n/(n + 1) = 1/(1 + 1) = 1/2 1/2 = 1/2 Inductive Step: ∑_{1}^{n+1} 1/j(j + 1) = (n + 1)/(n + 2)

∑_{1}^{n+1} 1/j(j + 1) = (n + 1)/(n + 2)  What you’re trying to prove
∑_{1}^{n+1} 1/j(j + 1) = ∑_{1}^{n} 1/j(j + 1) + 1/(n + 1)(n + 2) math
= n/(n+1) +1/(n+1)(n+2)  inductive hypothesis
= n(n + 2) + 1)/(n + 1)(n + 2)  math
= (n^{2} + 2n + 1)/(n + 1)(n + 2)  math
= (n + 1)/(n + 2)  math

QED