Solutions to midterm exercises

1. If D(x,y) is the predicate 'x divides y' then which of the following statements are true in the domain of positive integers?

2. Let P(x, y) be the predicate 'x is a parent of y', and let O(x,y) be the predicate 'x is older than y', and let the universe of all variables be the set of all people. Express each of the following statements as predicate logic formula using P and O:

3. True or False

f°g questions

4. Prove that gcd(a,b) = gcd(b, a mod b).

5. Define a function on the non-negative integers by g(0)=2. g(1)=3 and g(n+1)=3g(n)-2g(n-1). Use strong induction to prove g(n)=2n+1

Proof: Base case (n=1) works.
Inductive step:
g(n+1) = 3g(n)-2g(n-1) = 3*2n+3 - 2*2n-1-2 = 2n+1+1

6. If a and b are rationals, is a^b rational? Prove or disprove this conjecture.

7. Proof by induction:
1*20+2*21 + 3*22 + ... + n*2n-1 = (n-1)*2n+1

Basis case: n=1 works
Inductive step:
sum(k*2k-1) (k=1,n+1) = sum(k*2k-1) (k=1,n) + (n+1)*2n = (n-1)*2n+ 1 +(n+1)*2n = n*2n+1+1

8. ...