Solutions to midterm excersizes

Let us know if you find any errors :)

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. Find gcd(2n+1, 3n+2).
=gcd(2n+1, n+1) = gcd(n, n+1) = 1

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. Proof by contradiction: if x is a rational number and y is an irrational number, then x+y is irrational.
Suppose it's not the case, i.e. x+y = p/q Since x = r/s, y = p/q-r/s = (ps-rq)/qs - rational number!

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

Proof:
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. ...