Some Worked Chapter 3 problems

  1. Example 8 from P192 of the text says that we should prove that a finite set with n elements has 2^n subsets. Remember the first assignment in which we defined an algorithm (recursive) which defined a function which actually gave us the power set.

    Here is a recursive definition version of the same thing.

    X is in Power({}) iff X = {}
    X is in Power(S union {a}) iff (X is in Power(S)) or (X - {a} is in Power(S))

    It should be clear how to prove that Power(S union {a}) has 2^(n+1) elements if you assume that Power(S) has 2^n elements. I.e. each element X in Power(S) contributes precisely 2 elements to Power(S union {a}), namely X and X union {a}.

  2. Example 14 P. 197 as recursive set. Prove that every postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps.

    Well, let S denote the recursively defined set:
    -- 4,5 are both in S
    -- if x and y are in S, then so is x+y.

    It should be clear that a number is in S iff it is an amount that can be obtained using 4 and 5 cent stamps.

    Strong or second principle of Induction: [P(1) ^ ( [P(1) ^ P(2) ... ^ P(n)] --> P(n+1)) implies P(n) holds for all n>= 1.

    Sometimes with this second principle of induction we have to establish more than just the base step n=1. Not because the principle says you have to, but rather because we can only perform the proof of ( [P(1) ^ P(2) ... ^ P(n)] --> P(n+1)) for values of n larger than some fixed number. Then we need to go back and do the smaller values of n individually. Let's start with the inductive step and see what happens: We take some n>= 12 and assume that 11< k <= n implies that k is in S. i.e. we are assuming P(k) for each such k. Well if we knew that n-3 was in S, then, knowing that 4 is in S, we can deduce that (n-3)+4 = n+1 is in S. So this is valid for all n> 15 so to finish the proof we have to just check that 12, 13, 14, and 15 are in S some other way. Well, just use inspection:

    12=4+4+4, 13=4+4+5, 14=4+5+5, 15=5+5+5.

  3. 11 P198: Bernoulli's inequality: if h> -1, then for all nonnegative n

    1+nh <= (1+h)^n .

    Check this for n=0, 1 is <= (1+h)^0=1.

    Now assume it is true for some fixed n, and let's prove it for n+1. We must prove that 1+(n+1)h <= (1+h)^(n+1)
    and we can assume that 1+nh <= (1+h)^n. Don't forget we also know that n>= 0, and h>-1.
    Well, 1+(n+1)h = 1+nh + h < (1+h)^n + h by the inductive hypothesis.
    Now, look at (1+h)^(n+1) = (1+h)^n * (1+h) = (1+h)^n + h*(1+h)^n.

    So by the above two lines, it is enough to prove that h <= h*(1+h)^n.
    If h> 0, then this is equivalent to dividing both sides by h:
    1<= (1+h)^n which is true because 1+ h> 1 (in this case).

    Now assume that h=0, and just check that h = h*(1+h)^n.

    Finally assume that -1 < h < 0, and again divide both sides by h but this time reverse the inequality:
    1 >= (1+h)^n, which is true because 0< 1+h < 1.

  4. Question 20 on Page 199. Prove by induction on n that 3 divides n^3+2n whenever n is a positive integer.

    If n=1, then n^3+2n=3, so 3|3.
    Assume that 3 divides n^3+2n and now think about (n+1)^3+ 2(n+1).

    Well let's multiply it out to see if we can get the inductive assumption to help:
    (n+1)^3 + 2(n+1) = n^3+3n^2 + 3n+1 + 2n + 2 = (n^3+2n) + (3n^2+3n+1+2)
    Inductive assumption says that 3|(n^3+2n), so we just have to prove that 3|(3n^2+3n+3), which is obvious.

    Here's a nice proof without induction. It is equivalent to asking if n^3+2n is equal to 0 mod 3. Since 2 == -1 (mod 3) we can say that n^3 +2n == n^3 - n (mod 3) == n * (n^2 - 1) = n * (n-1) * (n+1) (mod 3). But this last expression is the product of 3 consecutive integers, so one of them is a multiple of 3!

  5. Similar to 53 P200. Use mathematical induction to prove that if gcd(b,a_i) = 1 for i=1,...,n, then gcd(b, a_1 * a_2 * ... * a_n)=1.

    It is very clear for n=1. Assume this is true for any list of numbers a_1, ..., a_k for any k less than or equal some fixed n. I.e. we are assuming P(1), ... P(n). Now consider n+1 numbers.
    We can write a_1 * ... * a_(n+1) as c * a_(n+1). By inductive hypothesis we have that gcd(b, a_1*...*a_n) =1 and by assumption we have that gcd(b,a_(n+1))=1. Now c * a_(n+1) is the product of 2 numbers and b is relatively prime to both of them. If n> 1, then we could just P(2) to deduce that gcd (b, c*a_(n+1) )=1. So this handles every case except n=1 and checking directly P(2). You don't often get away without having to actually prove something!

    This case, P(2), follows easily from the following result in the book: if d|(a*c) and gcd(d,a)=1, then d|c. So, assume that 1< d=gcd(b,a_1 * a_2). Now clearly d divides a_1 * a_2 and also b. Since gcd(b,a_1)=1, no divisor of d can divide a_1 (since it does divide b). Therefore, gcd(d,a_1)=1 and d| a_1*a_2, allows us to deduce that d|a_2, contradicting that gcd(b,a_2)=1.

  6. A recursive defined function on the integers means to define f(0) (and maybe a couple of other special cases, e.g. f(1), f(2)) and to then say that f(n) is defined in terms of earlier values of f, i.e. f(0), f(1), ..., f(n-1) (or we might give f(n+1) in terms of f(n), same difference).

    Question 6 P209. Give a recursive definition of a_n where

    1. a_n=4n-2. Well, a_0=-2 clearly. a_(n+1) is just 4 more than a_n, so a_(n+1)=a_n+4.
    2. a_n=1+(-1)^n. Hmm. a_0 = 2. a_1 = 0, a_2=2, ... So how about just a_0=2, a_1=0. Then a_n=a_(n-2) for n>1;.
    3. a_n=n(n+1). a_0=0, a_1=2. I don't see a trick. Let's look at a_(n+1) and see what to do to a_n to get it. a_(n+1) = (n+1)(n+2) = (n+2)(n+1) = n(n+1) + 2(n+1). So it looks like a_(n+1) = a_n + 2(n+1).

      But isn't that interesting, keep adding the twice the n'th number and the expression a_n results.

    4. a_n=n^2. Obviously a_0 = 0. Since (n+1)^2 = n^2+2n+1, we again get a_(n+1) = a_n + (2n+1)=a_n + 2(n+1)-1.

      Another summation formula for free: notice that by the recursive definition of a_n, a_n is equal the sum 1+3+...+(2n-1).

  7. f_n = f_(n-1) + f_(n-2), and f_0=0, f_1 = 1 are the fibonacci numbers. Prove that the sum of the squares of f_1, ..., f_n is equal to f_n * f_(n+1).

    Easy induction. Check it for n=1 directly. Ok, did you do it?
    Now assume it is true for all k <= n. The sum of the squares up to f_(n+1) is equal (by the induction hypothesis) to
    f_n * f_(n+1) + (f_(n+1))^2. Factor out f_(n+1) to get f_(n+1) * (f_n + f_(n+1)) and, hey!, that's the definition of f_(n+2).

  8. That was question 10 P209, is 12 any harder? It says to show that f_(n+1) * f_(n-1) - (f_n)^2 = (-1)^n.

    Check it for n=1 and why not do it for n=2 also just in case we need it. I'll wait a minute while you do that. Click here to continue

  9. We're back. Question 18 P210. Recursive definition of max(a_1,...,a_n) should probably just be:
    max(a_1,a_2) := a_1 if a_1< a_2, and equal a_2 otherwise
    max(a_1,a_2,...,a_(n+1)) := max( max(a_1,...,a_n), a_(n+1) ).

    But maybe maxbinary(a_1,...,a_n) might be more efficient:

    maxbinary(a_1,a_2) := max(a_1,a_2) (as above), and
    maxbinary(a_1,...,a_n) := maxbinary( maxbinary(a_1,...,a_m), maxbinary(a_(m+1), ..., a_n) ), where m = [(1+n)/2] just like in the binary search algorithm.

    Did you notice the glitch? I had better put in max(a_1)=a_1 or else put in a test for the case that n or m is just 1.

  10. Question 22 P210. Give a recursive definition of the set:
    1. {1,3,5,7,...}. base: 1 is in S. Generation: x in S implies x+2 is in S.
    2. {3,9,27,81,...}. Base: 3 is in S. Generation: x,y in S implies x*y is in S.
    3. The set of polynomials with integer coefficients. Base: 0 and 1 are in S. Generation: if p,q,r are in S, then so is p*x + q + r where x is the unknown.

      It is clear that everything in S is a polynomial with integer coefficients, but is it clear that every such polynomial is in S? Prove it by induction.

  11. How about bit strings: 0 is in S and if x,y are in S, then so are each of xy, 1xy, x1y, xy1.
      By induction:
    1. Prove that every member of S has more 0's than 1's.
    2. Prove that every bit string that has more 0's than 1's is in S.
    Click HERE for the proofs.
This is the end. The stuff below is from the question about f_(n+1) * f_(n-1) - (f_n)^2 = (-1)^n.