1. (4 points) Use induction to show n-1 34=4-4 for all positive integers n 2. i=1...

Transcribed Image Text:

1. (4 points) Use induction to show n-1 34=4"-4 for all positive integers n 2. i=1 2. (4 points) Suppose {a} is a sequence recursively defined by a = 1 and an+1 = 2an 2 for all integers n, n 1. Use induction to prove that ann2n-1 for all positive integers n. = 3. (4 points) Let A be a variation of the Ackermann function defined by 2n 0 if m = 0 if m1 and n = 0 A(m, n) = 2 if m1 and n = 1 A(m - 1, A(m, n 1)) if m 1 and n 2 Use induction to prove that A(1, n) = 2" for all positive integers n. 4. (a) (1 point) Give a recursive dedition of the set of positive integers that are not divisible by 4. (b) (1 point) Give a recursive definition of the set of positive integers that are powers of 2. 1. (4 points) Use induction to show n-1 34=4"-4 for all positive integers n 2. i=1 2. (4 points) Suppose {a} is a sequence recursively defined by a = 1 and an+1 = 2an 2 for all integers n, n 1. Use induction to prove that ann2n-1 for all positive integers n. = 3. (4 points) Let A be a variation of the Ackermann function defined by 2n 0 if m = 0 if m1 and n = 0 A(m, n) = 2 if m1 and n = 1 A(m - 1, A(m, n 1)) if m 1 and n 2 Use induction to prove that A(1, n) = 2" for all positive integers n. 4. (a) (1 point) Give a recursive dedition of the set of positive integers that are not divisible by 4. (b) (1 point) Give a recursive definition of the set of positive integers that are powers of 2.