## Math 310: Problem set 3

Instructions: This problem set is due Thursday, September 14, 2006. Your goal is not only to give correct answers but to communicate your ideas well. Make sure you use good English.
1. Read Chapter 3ABC of the text.
2. Consider 252x + 161y = 8. Use Euclid's algorithm to find integers x and y solving the given equation, or explain why no such integers exist.
• From class or by Proposition 4 on p. 34, we know that there is a solution if and only if gcd(252,161) divides 8. But as we saw in class, gcd(252,161) = 7, and since 7 does not divide 8, there is no solution.
3. Now consider 252x + 161y = 14. Use Euclid's algorithm to find integers x and y solving the given equation, or explain why no such integers exist.
• Let b = 252 and a = 161. Then as in class we have:
```
252 = 161*1 + 91    b -  a = 91
161 =  91*1 + 70   2a -  b = 70
91 =  70*1 + 21   2b - 3a = 21
70 =  21*3 +  7  11a - 7b =  7
21 =   7*3 +  0
```
Thus 22a - 14b = 14, so x = -14 and y = 22 is the solution given by Euclid's algorithm.
4. Use Euclid's algorithm to find [25]-1161.
• We must solve 25x + 161y = 1. This has a solution since gcd(161,25) = 1. Once we find x, then [25]-1161 = [x]161. So now we find x and y. Let b = 161 and let a = 11:
```161 = 25*6 + 11     b -  6a = 11
25 = 11*2 +  3   13a -  2b =  3
11 =  3*3 +  2    7b - 45a =  2
3 =  2*1 +  1   58a -  9b =  1
2 =  1*2 +  0
```
Thus x = 58, y = -9 gives a solution, so [25]-1161 = [58]161.
5. The goal of this problem is to use induction to prove that the sum of the first n odd numbers is n2; i.e., that 1 + 3 + ... + (2n-1) = n2 for every positive integer n.
• What is the sequence S(1), S(2), ... of statements we must verify?
• S(1) is the statement that 1 = 12; S(2) is the statement that 1 + 3 = 22, etc. S(n) is the statement that 1 + 3 + ... + (2n-1) = n2.
• Verify the base case (i.e., verify S(1)).
• S(1) is true since 1 = 12 is true.
• Verify the induction step; i.e., show why S(n) must be true if S(1), ..., S(n-1) are all true. (It's OK if you only need to use some of the statements S(1), ..., S(n-1). For this problem, in fact, you can show that S(n) is true using just S(n-1).)
• Assume that S(n-1) is true; i.e., assume that 1 + 3 + ... + (2(n-1)-1) = (n-1)2 is true. But 1 + 3 + ... + (2n-1) = 1 + 3 + ... + (2(n-1)-1) + (2n-1), and substituting (n-1)2 for 1 + 3 + ... + (2(n-1)-1) gives 1 + 3 + ... + (2n-1) = (n-1)2 + (2n-1), which simplifies to (n-1)2 + (2n-1) = n2 - 2n + 1 + 2n - 1 = n2. (Thus S(n) is true, hence S(i) is true for all i >= 1, as we wanted to prove.)
6. The goal of this problem is to use induction to prove that ai = 2i for every nonnegative integer i, given that a0 = 1, a1 = 2 and that an+1 = an + 2an-1 for each integer n > 0.
• What is the sequence S(0), S(1), ... of statements we must verify?
• S(0) is the statement that a0 = 20; S(1) is the statement that a1 = 21; etc. S(n) is the statement that an = 2n.
• Sometimes there's more than one base case. This time there are two: Verify the base cases (i.e., verify S(0) and S(1)).
• S(0) is true since a0 = 1 is given, and 20 = 1. S(1) is true s since a1 = 2 is given, and 21 = 2.
• Verify the induction step; i.e., for n>=1, show why S(n+1) must be true if S(0), ..., S(n) are all true. (It's OK if you only need to use some of the statements S(0), ..., S(n-1). For this problem, for example, you'll need to use the equation an+1 = an + 2an-1 to show that S(n+1) is true, whenever S(n) and S(n-1) are true.)
• We are given that an+1 = an + 2an-1. But by induction we can assume that an = 2n, and that an-1 = 2n-1. By substitution we get an+1 = an + 2an-1 = 2n + 2*2n-1, which simplifies to 2n + 2*2n-1 = 2n + 2n = 2*2n = 2n+1, which is what we wanted to prove. (Thus S(n+1) holds, so we have given a proof by induction that S(i) is true for all i >= 0.)