Harbourne's Math 310 Problem set 3

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.
- 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.
Use Euclid's algorithm to find [25]^-1₁₆₁.
- We must solve 25x + 161y = 1. This has a solution since gcd(161,25) = 1. Once we find x, then [25]^-1₁₆₁ = [x]₁₆₁. 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₁₆₁ = [58]₁₆₁.
The goal of this problem is to use induction to prove that the sum of the first n odd numbers is n²; i.e., that 1 + 3 + ... + (2n-1) = n² 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²; S(2) is the statement that 1 + 3 = 2², etc. S(n) is the statement that 1 + 3 + ... + (2n-1) = n².
- Verify the base case (i.e., verify S(1)).
  - S(1) is true since 1 = 1² 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)² is true. But 1 + 3 + ... + (2n-1) = 1 + 3 + ... + (2(n-1)-1) + (2n-1), and substituting (n-1)² for 1 + 3 + ... + (2(n-1)-1) gives 1 + 3 + ... + (2n-1) = (n-1)² + (2n-1), which simplifies to (n-1)² + (2n-1) = n² - 2n + 1 + 2n - 1 = n². (Thus S(n) is true, hence S(i) is true for all i >= 1, as we wanted to prove.)
The goal of this problem is to use induction to prove that a_i = 2ⁱ for every nonnegative integer i, given that a₀ = 1, a₁ = 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₀ = 2⁰; S(1) is the statement that a₁ = 2¹; etc. S(n) is the statement that a_n = 2ⁿ.
- 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₀ = 1 is given, and 2⁰ = 1. S(1) is true s since a₁ = 2 is given, and 2¹ = 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 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ⁿ, and that a_n-1 = 2^n-1. By substitution we get a_n+1 = a_n + 2a_n-1 = 2ⁿ + 2*2^n-1, which simplifies to 2ⁿ + 2*2^n-1 = 2ⁿ + 2ⁿ = 2*2ⁿ = 2ⁿ⁺¹, 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.)