## 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.
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.
4. Use Euclid's algorithm to find [25]-1161.
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?
• Verify the base case (i.e., verify S(1)).
• 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).)
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?
• 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)).
• 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.)