- 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.
- 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.

- 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.

- Let b = 252 and a = 161. Then as in class we have:
- Use Euclid's algorithm to find [25]
^{-1}_{161}.- We must solve 25x + 161y = 1. This has a solution since
gcd(161,25) = 1. Once we find x, then [25]
^{-1}_{161}= [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]^{-1}_{161}= [58]_{161}.

- We must solve 25x + 161y = 1. This has a solution since
gcd(161,25) = 1. Once we find x, then [25]
- 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?
- S(1) is the statement that 1 = 1
^{2}; S(2) is the statement that 1 + 3 = 2^{2}, etc. S(n) is the statement that 1 + 3 + ... + (2n-1) = n^{2}.

- S(1) is the statement that 1 = 1
- Verify the base case (i.e., verify S(1)).
- S(1) is true since 1 = 1
^{2}is true.

- S(1) is true since 1 = 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).)
- 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) = n^{2}- 2n + 1 + 2n - 1 = n^{2}. (Thus S(n) is true, hence S(i) is true for all i >= 1, as we wanted to prove.)

- Assume that S(n-1) is true; i.e., assume
that 1 + 3 + ... + (2(n-1)-1) = (n-1)

- What is the sequence S(1), S(2), ... of statements we must verify?
- 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?
- S(0) is the statement that a
_{0}= 2^{0}; S(1) is the statement that a_{1}= 2^{1}; etc. S(n) is the statement that a_{n}= 2^{n}.

- S(0) is the statement that a
- 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 a
_{0}= 1 is given, and 2^{0}= 1. S(1) is true s since a_{1}= 2 is given, and 2^{1}= 2.

- S(0) is true since a
- 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.)- We are given that a
_{n+1}= a_{n}+ 2a_{n-1}. But by induction we can assume that a_{n}= 2^{n}, and that a_{n-1}= 2^{n-1}. By substitution we get a_{n+1}= a_{n}+ 2a_{n-1}= 2^{n}+ 2*2^{n-1}, which simplifies to 2^{n}+ 2*2^{n-1}= 2^{n}+ 2^{n}= 2*2^{n}= 2^{n+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.)

- We are given that a

- What is the sequence S(0), S(1), ... of statements we must verify?