For induction questions. The usual set up: make a statement P(n). Prove that P(0) or P(1) (and maybe a few more are true) and then fix an integer n>= the last one you checked. Might as well do strong induction, assume that P(j) is true for all j< n+1, and now try to prove that P(n+1) is true (usually using somewhere critically that P(j) is true for some j< n+1).
• 3.2 P198: 4 SUM( 2(-7)^k : k=0..n) = [1 - (-7)^(n+1)]/4

In this case P(n) is of course the statement that SUM(2(-7)^k : k=0..n) is equal to [1 - (-7)^(n+1)]/4.

Substitute n=0 to see if P(0) is true: SUM(2(-7)^k :k= 0..0) is equal to 2(-7)^0 = 2. While [1 - (-7)^1] /4 = 2. So it, i.e. P(n), is true for n=0.

Now assume n is greater or equal 0, and that P(j) is true for all 0<= j < n+1.
SUM up to n+1 is equal to SUM up to n plus the (n+1)-st term so
SUM( 2 (-7)^k : k=0... n+1) = [1-(-7)^(n+1)/4 + 2 (-7)^(n+1) by the inductive assumption. [1-(-7)^(n+1)/4 + 2 (-7)^(n+1) = [1 - (-7)^(n+1) + 8 (-7)^(n+1)] / 8 = [ 1 + 7 * (-7)^(n+1)] / 4 = [1 - (-7) * (-7)^(n+1) ] / 4 .

6 SUM( 1/k(k+1) : k=1..n) = ?
We compute the values for n=1,2,...; and we get the sum equal
1/2; 1/2+1/6=4/6=2/3; 2/3 + 1/12 = 9/12 = 3/4; 3/4 + 1/20 = 16/20 = 4/5; The pattern looks like n/(n+1).

Let P(n) be the statement that SUM( 1/k(k+1) : k=1..n) = n/(n+1).

We've already checked n=1, n=2, .., n=4.

By induction assume that n>3 and that P(j) is true for all j<n+1. We wish to now verify that P(n+1) holds.

Clearly SUM( 1/k(k+1) : k=1.. n+1) = SUM( 1/k(k+1) : k=1.. n) + 1/(n+1)(n+2). By inductive assumption P(n) we have that this sum is then equal to n/(n+1) + 1/(n+1)(n+2). Put these over the common denominator to get
[n(n + 2)+1]/(n+1)(n+2) = [ n^2 + 2n + 1 ] / (n+1)(n+2) = n+1 / n+2

12 3^n <n!
We should know (easily guess) that from some point on the RHS will be larger than the LHS since the inductive step (from n to n+1) changes the LHS by multiplying by 3 while it multiplies the RHS by n+1, hence it is a reasonable guess that the RHS will eventually be bigger.

Trying values we find that if n=6, then 3^6 = (27)^2 = 729 and 6!=720, OK not yet but then n=7 gives 3^7 = 3*729 = 3*720 + 3*9 and 7! = 7 * 720 = 3*720 + 4*720, clearly much bigger.

Now assume that n> 6 and that 3^j < j! for all 6 < j < n+1. This is easy now: 3^n < n! by inductive assumption, hence 3*3^n < 3 * n! which in turn is less than (n+1) * n! since 6< (n+1).

20 3|n^3+2n
We can do this easily using mod 3 arithmetic. n^2+2n = n(n^2+2). But now, a trick, 2 is the same as -1 mod 3, hence, MOD 3, this equals n(n^2-1) = n(n-1)(n+1). This is the product of 3 consecutive integers, one is divisible by 3.

To do this by induction, check that 1^3+2*1 = 3 is divisible by 3. Assume that for some integer n> 0, n^3+2n is divisible by 3. Look at (n+1)^3 + 2(n+1) and try to see if the previous term, n^3+2n can help. (n+1)^3 = n^3 + 3n^2 + 3n + 1 (the binomial coefficients). Hence (n+1)^3+2(n+1) = n^3 + 2n + [3n^2 + 3n + 1 + 2]. By inductive assumption n^3+2n is divisible by 3 and by inspection, 3n^2 + 3n + (1+2) is divisible by 3.

• 3.3 P209 12 f_n+1 f_n-1 - f_n^2 = (-1)^n
Check it for n=1 (I will leave that for you).
Assume this equation is true for all j< n+1 (0< j of course). Let's consider the case for n+1: we need to simplify
f_(n+2) * f_(n+1-1) - f_(n+1)^2.

Well we just play around with this (i.e. replacing f_m by f_(m-1) + f_(m-2)) whenever you want to see if you can get somewhere with it. It took me a little while before I thought of replacing just one of those f_(n+1)'s. I knew we didn't want f_(n+2) in there.

f_(n+2) * f_n - f_(n+1)^2 = ( f_(n+1) + f_n ) * f_n - f_(n+1) * ( f_n + f_(n-1) ) =
cancel terms = f_n^2 - f_(n+1) * f_(n-1) = - [f_(n+1) f_(n-1) - f_n^2 ] = - (-1)^n by induction hypothesis.

• 3.4 P217: 4 max of finite set; but ensure O(log n) To try to get O(log(n)) let's use divide and conquer.
```    Procedure RecMax([a_1,..., a_n] : list)
x := RecMax([a_1, ..., a_{floor(n/2)}])
y := RecMax([a_{floor(n/2) +1}, ..., a_n])
if x< y then output y
else output x
```
If we let f(n) denote the number of steps needed to find the maximum of a list with n elements, then for n an even number, we have the recurrence relation: f(n) = 2 f(n/2) + 1

In this case, from our book formula f(n) = a f(n/b) + C, we have that a=2 and b=2, hence our algorithm is O(n^{log(2)})= n.

I suppose it's clear we can't get O(log(n)) steps since we have to at least READ every element of the list.

18 recur. alg for a_n where a_n = sum of prev. 3 and starts with 1,2,3
Procedure SumOf3(n) if n> 2 then output SumOf3(n-1) + SumOf3(n-2) + SumOf3(n-1) else begin if n=0 then output 1 else if n=1 then output 2 else output 3 end

• Review P228: 40 rec. alg for gcd
Procedure GCD(a,b) if a< b then GCD(b,a) else begin r := a - b * floor(a/b) if r := 0 then output b else GCD(b,r) end

41 f(n)=f(n-1) +2n -1, f(1)=1 then use A3 to test
2n-1 is the n-th odd integer, f(1)=1, f(2) = f(1) + 3; f(3) = f(2) + 5 = 1 + 3 + 5; ... . Use Gauss' idea: (1+3+5+ ... + 2n-1) * 2 = (1+3+5+...+2n-1)+(2n-1 + ... + 3 + 1) = ( 2n + 2n + ... + 2n)= 2n^2. So (1+3+...+ 2n-1) = 2n^2 / 2 = n^2

Prove by induction: P(n) is the assertion that f(n) = n^2. Clearly P(1) is true. Assume that n is some positive integer and that P(n) is true. f(n+1) = f(n) + (2(n+1)-1) = (by induction) = n^2 + 2(n+1) - 1 = n^2 + 2n + 1 = (n+1)^2.

Now try Section A3 for more practice. To reduce confusion, let a_n denote f_n. We can set a_0 = 0 and still have that a_1 = a_0 + 2(1) - 1, hence our recursion holds for all n> 0.

Let the generating function for {a_n} be denoted by g(x) and do the usual thing:
g(x) = 0 + SUM( a_n x^n : n=1...) = SUM ( (a_(n-1) + 2n-1) x^n : n = 1 ...)
g(x) = x g(x) + 2 * SUM( n x^n : n=1...) - x * SUM(x^n : n=0...) = x g(x) + 2x * SUM( n x^(n-1) : n=1...) - x/(1-x)

At this point we have to notice/recall that SUM(n x^(n-1) : n=1...) is just the derivative of SUM( x^n : n=0...), hence it is equal to 1/(1-x)^2. So

g(x) = x g(x) + 2x * 1/(1-x)^2 - x/(1-x). Now solve for g(x).
g(x) * (1-x) = [2x -(1-x)*x]/(1-x)^2, then g(x) = [x^2 + x]/(1-x)^3.

Well we didn't do any like this (but on the other hand we know the answer already): g(x)= [x^2 +x ] /(1-x)^3 = 2x^2/(1-x)^3 + (x-x^2)/(1-x)^3 = 2x^2 / (1-x)^3 + x/(1-x)^2.

We broke it up like this because 2/(1-x)^3 is the derivative of 1/(1-x)^2 and so is the second derivative of 1/(1-x). Similary 1/(1-x)^2 is the derivative of 1/(1-x). Thus we have that g(x) = x^2 * d^2[ 1/(1-x) ]/dx^2 + x * d[1/(1-x)]/dx.
Then g(x) = x^2 * SUM( n(n-1) x^(n-2) : n=2...) + x * SUM( n x^(n-1) : n=1...) =
= SUM ( n(n-1) x^n : n=2...) + SUM( n x^n : n=1...) = SUM ( [n^2-n+n] x^n : n=1...) ( a little fiddling with n=1) = SUM( n^2 x^n : n=1...) as required.

42 twice the 0's = the 1's.
I don't have my book, I assume we are to write an inductive definition of the set S of all bit strings with twice as many 1's as 0's. Clearly we need a generation rule which will involve adding two 1's and one 0 to one or more strings which already have the right property. To get strings like 001111111100 we cannot just stick the new bits at the beginning or end old ones but we have to be prepared to put in between as well. E.g. the above can be gotten with 0 011 11 111100 where both 011 and 111100 have the right property. Let's give this a try:
1. base: lambda is in S (I guess 2 times 0 = 0 qualifies)
2. generation: if x and y are both in S then so are: xy, 0 x 1 y 1, 1 x 0 y 1 and the reverse of these two strings.

I hope it's enough. Exercise 1: prove by induction that every string in S has twice as many 1's as 0's. I.e. true for base, assume it is so for x, y in S, then it is so for the new ones added by the generation rule.

Exercise 2: Prove that if z is any string with twice as many 1's as 0's then z is in S. We cannot induct on the generation rule for S since we are supposed to let z be any string at all; by only talking about the rules for S then we may not be considering all possible z. The best attack is to say P(n): every string z of length n with twice as many 1's as 0's will be in S. Prove P(0), P(1), P(2) by inspection (we do the first 3 because we anticipate that we will be subtracting 3 from the length of z).

Now suppose that n+1 is an integer > 2 and that P(j) is true for all j such that 0<= j < n+1. I.e. if y is any string of length at most n which has twice as many 1's as a 0's, then y is in S. Let z be any string of length n+1 which has twice as many 1's as 0's. We have to examine cases (how z starts or ends) to see which generation rule for S will be of help.

1. Case 1: z starts with a 0 and ends with 2 1's or the reverse of this.
This case is very easy. z will be of the form 0x11. We can note that x is in S by the inductive hypothesis (most important step) since x is shorter and has the right balance of 0's and 1's. Now just use the rule for S with y = lambda.

2. Case 2: z starts with a 0 and ends with a 01 (or the reverse).
Somehow we've got to recognize z as 0x1y1 or xy in which x and y are also "0-1" balanced. This is the old trick of keep the running count of 2*(#of 0's) - #of 1's as you run from left to right. We start with a 0 so this quantity starts out as 2. We know it ends with the zero value, hence just before counting that last 0 it had the value of -1. It only decreases when you pass a 1 hence there is a shortest string x, such that the count after passing 0x1 in the initial part of z, we have the count equal to -1. Let y be the rest of z except for that last 1, hence z = 0x1y1 (but the exact definition of x is very important). But it seems that 0x has the right balance of 0's and 1's and therefore, so too does 1y1. As before, 0x and 1y1 are shorter and have the right balance of 0's and 1's, hence by the strong induction assumption both are in S. To be clear: set x' = 0x and y' = 1y1, hence x' and y' are strings in S, for which the S-rule says that x' y' = z is in S.
3. Case 3: z starts with a 0 and ends with a 0.
Similar. Start at the left and compute 2*(# of 0's) - (# of 1's). We start with a +2 after the first 0 and must have a -2 just before counting the last 0. Somewhere in between we had a 0. Again this splits z into x,y both of which, by induction, are in S.
4. Case 4: z starts and ends with a 1. That same quantity starts out as -1 and just before the last step it is a +1. Thus somewhere in between it passes from negative to non-negative - BUT it jumps up by 2's so it may have gone from -1 to 1 or from -2 to 0. In the latter case, we can again break it in the form xy = z where the end of x is just the spot where it became 0. This puts z in S just as above. Otherwise find that special 0 which makes it jump from -1 to 1, thus z = 1 x 0 y 1 where the 1x is the string just before that special 0. Check out the values to see that x and y are properly balanced, hence are in S. Thus the generation rule for S puts z in Z.
In hindsight, it looks like xy, 0x11, 11x0, and 1x0y1 would have worked.

43 lambda, 0x, x1 for x in S so what's S?

Try constructing S for a while to get the pattern. S_0 = {lambda,0,1}. S_1 = {lambda, 0, 1, 00, 01, 01, 11} repetitions since I just took x through S_0 and applied rules for each x. S_2 = { lambda, 0, 1, 00, 01, 11, 000, 001, 011, 001, 011, 111} = {lambda, 0,1, 00, 01, 11, 000, 001, 011, 111}

Ready to guess? S is all strings of the form 00...0011...1 (where there can be no 0's and no 1's). I.e. no 0 is to the right of any 1.

Prove it by induction: First every string in S has this form: if x has the form then certainly 0x and x1 do as well.

Conversely P(n): if s is a string of length n in which no 0 is to the right of a 1, then s is in S. P(0) and P(1) are clear.

Assume P(n) and prove P(n+1). Let s be a string. If all 1's then s = x1 for a string x with one fewer 1. By inductive assumption, x is in S, hence by S-rule, x1 is in S. If s has a 0, then the left most character of s is a 0. Therefore s has the form 0x and by inductive assumption x is in S (again it is shorter and certainly doesn't have a 0 to the right of a 1).

44 abc bac acb and abcx abxc xabc axbc are in S, show that every member of S has length divisible by 3.

Easy induction. I'm thinking a great question is to prove that for every every integer j, there is an s in S such that s has j consecutive a's in it.

• 4.2 P248: 4 d+1 cons. integers gives 2 with same remainder when divided by d.

d+1 consecutive numbers means some b, b+1, ..., b+d. Send each to its remainder mod d means is a function (pigeons to holes) which sends d+1 numbers to d possible values (some r between 0 and d-1). Therefore two are sent to the same value. (Consecutive didn't matter)

8 5 integer pairs in plane gives two such that midpoint of line segment is integer.

Let (xi, yi) for i=1...5 denote the 5 integer pair points in the plane. What is the formula for the midpoint of the line segment joining (xi, yi) to (xj, yj). Well the slope is m = (yj - yi) / (xj - xi). Half way along the x-axis from these two points takes you to xi + (xj - xi)/2 = (xi + xj) /2. Take that value for x and plug into the equation for the line which is y - yi = m ( x - xi). OK, so y - yi = m ( (xi+xj)/2 - xi) = m (xj - xi)/2 and since m has a denominator equal to xj - xi we get
y- yi = (yj-yi) /2 so y = (yi+yj)/2 (i.e. the midpoint (centre of mass) is just the average of the x-coords and the average of the y-coords).

Summarizing the above analysis (pigeon hole almost always involves some analysis of the problem before applying the Principle).
The midpoint between point i and point j is M(i,j) = ( (xi+xj)/2 , (yi+yj)/2 ). This is a pair of integers if we can divide by two which simply means xi and xj should both be even or both be odd and similarly for the y values. Construct 4 pots to send the values of i=1...5.

• P1 is x coord odd, y coord odd;
• P2 is x coord even, y coord odd;
• P3 is x coord odd, y coord even;
• P4 is x coord even, y coord odd.
• There are no other choices, hence each of the 5 numbers go to one of these pots. Two, say i,j, go to the same pot, hence M(i,j) has integer coordinates.