Lesson 10

Warning: It’s not unusual to find these problems really tough. One difficulty is that these problems

will make some demands on your algebra skills. Another difficulty is just getting the format of an

inductive proof correct. Here are a few suggestions concerning that: (1) Be sure to check the basis

case; (2) At the start of the inductive step, clearly state the inductive hypothesis; (3) After stating

the inductive hypothesis, write down what you need to prove; (4) Point out clearly where you apply

the inductive hypothesis in the proof of the inductive step.

(1) Use induction to prove: For every integer n ≥ 1,

1 · 2 + 2 · 3 + 3 · 4 + · · ·+ n(n + 1) = n(n + 1)(n + 2) 3

.

(2) Use the first form of induction (see example 16.5) to show that using only 4c/ stamps and 7c/ stamps, any postage amount 18c/ or greater can be formed.

(3) Redo the previous problem using the second form of induction (see example in the text). The basis step is just a bit messier this time, but the inductive step is much easier.

(4) A sequence is defined recursively by the rules: (1) a0 = 0, and (2) for n ≥ 1, an = 2an−1+2. Use induction to prove an = 2

n+1 − 2 for all n ≥ 0.

(5) Use induction to prove: For every integer n ≥ 1, the number n5 − n is a multiple of 5.

9

Hint: An integer is a multiple of 5 if it is 5 times some integer. For example, 165 = (5)(33) so 165 is a multiple of 5.

(6) (bonus) Here is a proof that for n ≥ 0, 1 + 2 + 22 + · · ·+ 2n = 2n+1.

Proof. Suppose 1 + 2 + 22 + · · ·+ 2n = 2n+1 for some n ≥ 0. Then 1 + 2 + 22 + · · ·+ 2n + 2n+1 = 2n+1 + 2n+1 using the inductive hypothesis

= 2(2n+1) = 2n+2 = 2(n+1)+1,

as we needed to show. �

Now, obviously there is something wrong with this proof by induction since, for example, 1 + 2 + 22 = 7, but 22+1 = 23 = 8. What specifically is wrong with the proof?

11. Lesson 11

For the proofs requested below, use facts and theorem given in this lesson, including results given

in the exercises, as justifications. Assume all letters represent integers.

(1) Mimic the proof given in the sample solutions for the proposition if a > 0 and b > 0, then ab > 0 to prove:

(a) If a < 0 and b < 0, then ab > 0.

(b) If a < 0 and b > 0, then ab < 0.

(2) Prove that is m2 = n2, then m = n or m = −n. (Hints: (1) From algebra: a2 − b2 = (a + b)(a− b), and (2) From exercises: If ab = 0, then either a = 0 or b = 0.)

(3) Determine all the integers that 0 divides. Hint: Think carefully about the definition of the divides relation! This question is

about the divides relation, not about the arithmetic operation of division (a maybe subtle distinction). The correct answer is probably not what you might first think it is.

(4) Prove: For integers r, s, t,and u, if r|t and s|u, then rs|tu.

(5) Determine the quotient and remainder when 117653 is divided by 27869. (Finally, an easy problem.)

(6) (bonus) Prove or give a counterexample: If p is a prime, then 6p + 1 is a prime.

12. Lesson 12

(1) Use the Euclidean Algorithm to compute the following gcd’s:

10

(a) gcd(216, 111).

(b) gcd(1001, 11).

(c) gcd(663, 5168).

(d) gcd(1357, 2468).

(e) gcd(733103, 91637).

(2) If p is a prime, and n is any integer, what are the possible values of gcd(p, n)? Hint: Try a few experiments with specific numbers to spot the correct answer. Alternatively, think about the positive integers that can divide a prime. Warning: In the notation gcd(a, b), do not assume that a ≥ b. The two parameters a and b can be written in either order: gcd(15, 12) = gcd(12, 15) = 3.

(3) Determine gcd(6123, 2913) and write it as a linear combination of 6123 and 2913.

(4) What can you conclude about gcd(a, b) if there are integers s, t such that as + bt = 8?

(5) What is the smallest positive integer that can be written as a linear combination of 2191 and 1351?

(6) (bonus) If n is a positive integer, what is gcd(n, n + 1)? Explain your answer.