### Quiz 2 review

1. P225 #8 Using induction, find n so that 11n+17 < 2^n.

Try a few values, here's a table:

```n         1       2       3       4       5       6       7
11n+17    28      39      50      61      72      83      94
2^n       2       4       8       16      32      64      128

```
The pattern is clear, for 11n+17 we just keep adding 11, but once n is larger than 3, going from 2^n to 2^(n+1) adds much more than 11, but we have to wait till 2^n catches up.

Prove, by induction, that P(n): 11n+16 < 2^n for n>6.

Base step: n=7 has been verified above.
Induction: Assume n>6 and 11n+17 < 2^n. We must show that P(n+1) holds. Look at 11(n+1)+17 = 11n + 17 + 11, which by induction, is less than 2^n+11, and since n>6>4, it follows that 2^n+11<2^(n+1) which completes the proof.

2. P225 #9. Postage using 5 and 9 cent stamps is the same as defining S recursively by: 5,9 are in S and for x,y in S , x+y is in S .

We can prove by induction that S contains everything bigger than some N, if we can establish that each of N, N+1, N+2, N+3, and N+4 are in S . Because then to show that n+1 is in S we just argue, by induction, that (n+1)-5 is in S . This is easy. I don't think we get 31 in S. 32=27+5, 33=15+18, 34=25+9, 35, 36 are obvious.

3. P225 #17. Recursively define gcd(a,b).

We need some fact about gcd(a,b) in terms of smaller values. For example, gcd(a,b) = gcd(a-b,b). So here goes:

gcd(a,b) = a if a=b

and gcd(a,b) = gcd(a-b,b) if a>b, else gcd(a,b)=gcd(a,b-a).

4. P226 #8: u_1=1, u_2=2. Recursively, having decided if each k < n is equal to u_j for some j, we set n to be the next Ulam number if it can be expressed in exactly one way as a sum of two distinct smaller Ulam numbers.

So u_3=3, u_4=4 (even though u_2+u_2 =4 but these are not distinct Ulam numbers), but 5 is not an Ulam number since 2+3 and 1+4 are both equal 5. u_5=6 (=u_2+u_4), 7 is out because 6+1 and 3+4. So far: 1,2,3,4,6 ; it looks like 9 is the next.

Prove by induction that there are infinitely many. It's better to do this by the well-ordering principle. Suppose that n is the smallest number such that there's no Ulam number bigger than n. So n=u_k for some k and we know that k> 2. Now clearly u_k + u_(k-1) is bigger than u_i+u_j for all other pairs j<=k and i< (k-1). Since we are assuming there are no other Ulam numbers, this would seem to imply that u_k+u_(k-1) is an Ulam number. ( Note that this does not prove that u_k+u_(k-1) is always an Ulam number. For example u_4+u_3 = 7 is not one).

5. P226 #10. Prove that P(n): 1^3 + ... + (2n+1)^3 = (n+1)^2 (2n^2 + 4n + 1) for all n>0.

Base case: n=1; plug n=1 into LHS, 1^3+(2+1)^3 = 28. Now the RHS, (2)^2 (2+4+1) = 4*7=28. So P(1) holds.

Assume that P(n) holds. Consider LHS of P(n+1) which is
1^3 + ... + (2n+1)^3 + ( 2(n+1) +1)^3.
By the induction hypothesis (P(n)) this is equal to (n+1)^2 * (2*n^2 + 4*n + 1) + ( 2*(n+1) +1)^3.

We don't need to be fancy, just carefully multiply and simplify:
2n^4+ 16n^3 + 47n^2 +60n+ 8
While the right hand side of P(n+1) is ( (n+1) +1)^2 * (2*(n+1)^2 + 4*(n+1) +1) which expands as
Well, what do you know (I used maple), the same thing. This completes the proof.

6. P226 #14. Prove 2^n > n^2+n for all n> 4.

Check Base case n=5: 2^5=32. 5^2+5 = 30. So we are ok.

By induction: n> 4 and P(n) holds. We want to show 2^(n+1) > (n+1)^2 + (n+1). Well, 2^(n+1) = 2*2^n which, by induction, is greater than 2*(n^2+n). To finish the proof, we just have to prove that 2*(n^2+n) is greater than (n+1)^2 + (n+1). This isn't true for all n, but we only need it for n> 4. This is quite routine.

7. P226 #21 the fibonacci number f_n is even iff ???

Here's the sequence 0 1 1 2 3 5 8 13 21 34 55 89 144

Well the pattern is clear: f_n is even iff n is a multiple of 3, i.e. if n == 0 (mod 3). It should even be clear why that's true (if you were the one who wrote down the sequence, it would have come to you).

Proof by induction: P(n) is the statement f_n is even iff n==0(mod 3)

P(0) or P(1) is clearly true.

Now assume that P(k) is true for all k at most n for some n>0. To prove P(n+1), there are three cases to check and once you realize that it is quite easy: n+1==0 (mod 3), n+1==1(mod 3), n+1==2(mod 3).

As is standard when a proof relies on more than just the previous case we have to check more than just the first case by hand. We did n=0, n=1 already, and we can see P(2), P(3) are also true. So now we can assume that n>= 3. Each case is similar. Suppose that n+1==0 (mod 3). Then f_(n+1) = f_n + f_(n-1). What about the congruence class of n and n-1? Well they are -1=2 and -2=1 respectively. Therefore, f_n and f_(n-1) are both odd, which of course means that f_(n+1) is even. Since n+1==0 (mod 3) this verifies P(n+1) for this case.

Case n+1==1(mod 3). In this case n==0(mod 3) and n-1==2(mod 3). Therefore f_n is even and f_(n-1) is odd. This means that f_(n+1) is odd which again verifies P(n+1) for this case.

The last case is similar.

8. P227 #40. This question is asking for a recursive algorithm for finding s and t so that gcd(a,b)=s*a + t*b. (You probably wish you had one for the last test!)

Up above we developed a recursive algorithm for gcd(a,b) so let us see if that helps. Basically it was that

gcd(a,b) = gcd(a-b,b). So if we had gcd(a-b,b) = s' * (a-b) + t' * b, then just multiply it out so that we have
gcd(a,b) = s' * a + (t'-s') * b.

Here goes then: Let us use S(a,b) to denote the coefficient of a and T(a,b) to denote the coefficient of b in the equation:

gcd(a,b) = S(a,b) * a + T(a,b) * b.
Base step: if a=b, then S(a,b)=a and T(a,b) = 0.

If a< b, then gcd(a,b) = gcd(b,a), so recursive call to next case:
if a> b, then S(a,b) = S(a-b,a) and T(a,b) = T(a-b,b) - S(a-b,b).

9. P227 #42. Given a bit string w, let us use w(0) to denote the number of 0's in w, and w(1) to denote the number of 1's. We are to recursively define the set S of those strings that have w(0)=2*w(1).

Imagine that you have such a string, w , in front of you and you are trying to see how it is constructed from a couple of shorter strings of that form. That is how you get a recursive definition. It's clear that if w has a 1 and a couple of 0's in the first or last couple of spots then w is of the form 0w'10 or 1w'00, etc. So a generation rule like: if w' is in S, then each of 100w', 10w'0, and a few more like that will get all of this type. But what if w starts and ends with a long string of 0's or starts and ends with a long string of 1's. Then we expect that w is obtained by sticking a couple of strings together. For example how do you get 000111000 or 100101001? It looks like the only reasonable way is:

` 0   001  1   100  0     and   1 001 0 100 1 .`

So here goes:

Base: the empty string is in S. Generation: if w and w' are in S, then so are (I'm not sure if this is the shortest possible list):

001w rearranged in any order, i.e. 0 w 01, 1w00, ...

and w w', and 001ww' again arranged in any order.

It is easy to prove by induction that every member, w of S has the property that w(0) = 2*w(1).

Clearly every quite short string satisfying the property is in S. So let us assume, by induction, that w is a string such that w(0) = 2*w(1) and that every shorter string which has twice as many 0's as 1's is in S. We must prove that w is in S.

If w doesn't start and end with a 1, or start and end with two 0's then it is easy to see how to get it as some substring (3 shorter) in S with 2 0's and a 1 stuck at the right places beginning and end. Hence in those cases, w is in S. Therefore we assume w begins and ends with 2 0's. I'll leave the begin and ends with a 1 since it is similar.

Suppose that w has n elements for some n. For each integer 0<k< n, let wk denote the string consisting of the first k elements of w. For each k, consider the quantity 2*wk(1) - wk(0)
. We are assuming that 2*wk(1) - wk(0) = 0 when k=n. Notice also that 2*wk(1) - wk(0) is 2 when k=n-2 and is equal to -2 when k=2. This quantity jumps up by 2 when the k-th member of w is a 1 and it drops by 1 when the k-th member of w is a 0. There is a smallest k (<n-2), where 2*wk(1) - wk(0) first becomes non-negative. If 2*wk(1) - wk(0) is equal to 0, then wk is in S and so is the tail of w with wk removed. On the other hand if 2*wk(1) - wk(0) is equal to 1, then set v to be the substring of w by going from position 2 to k-1 and let w' be the substring from position k+1 to n-1 and figure the argument that

`w  =  0   v   1  w'  0   is in S`