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]-1161.
- 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).)
- 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.)