## 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.
- Read Chapter 3ABC of the text.
- 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.
- 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.
- Use Euclid's algorithm to find [25]
^{-1}_{161}.
- The goal of this problem is to use induction to prove that the sum
of the first n odd numbers is n
^{2}; i.e., that
1 + 3 + ... + (2n-1) = n^{2} 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).)

- The goal of this problem is to use induction to prove that
a
_{i} = 2^{i} for every nonnegative integer i,
given that a_{0} = 1, a_{1} = 2 and that
a_{n+1} = a_{n} + 2a_{n-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 a
_{n+1} = a_{n} + 2a_{n-1}
to show that S(n+1) is true, whenever S(n) and S(n-1) are true.)