MATH/CSE 1019 Final Examination
Fall 2011
December 17, 2011
Instructor: S. Datta
1. (2 points) Evaluate the infinite geometric series
9 9 9
+ + + ...
10 100 1000
Note that the left hand side is 0.99 . . .. Use the answer above to fill in the blank below
a 0.9
Solution: This is a geometric series with a = 0.9 and r = 0.1. So the infinite sum is 1−r = 1−0.1 = 1.
0.99 . . . = 1.
2. (2 points) Express the following statement in predicate logic: “given any 2 distinct rational numbers, there
exists a rational number between them in value”.
Solution: Make the domain Q, the set of rational numbers. Then, the given statement is
∀x∀y[(x 6= y) → (∃z(x < z < y) ∨ (x > z > y))].
3. (2 points) Prove that if f : Z+ → Z, f (n) = n2 − 100n then f (n) ∈ Ω(n2 ).
Solution: Note that n2 − 100n ≥ n2 /2 if n ≥ 200. So we use n0 = 200, c = 0.5 in the definition of Ω(n2 )
and thus f (n) ∈ Ω(n2 ).
4. (2 points) What is the negation of ∀x∃yP (x) → Q(y). Your answer should not have negation symbols
before quantifiers and no implication symbols.
Solution: First we rewrite the given statement as ∀x∃y(¬P (x) ∨ Q(y)). Then we can negate this in the
usual way and get
∃x∀y(P (x) ∧ ¬Q(y))
5. (2 points) Write down the function that the following recursive algorithm computes and give a 1-sentence
justification for your answer. Assume that n is a positive integer.
Mystery(n)
1 if n = 1
2 then return 1
3 else return (n + Mystery(n − 1))
Pn n(n+1)
Solution: The program computes i=1 = 2 .
Each recursive call adds the previous number, stopping at 1, so it computes the sum n + (n − 1) + . . . + 2 + 1.
6. (3 points) Prove using induction the inequality n < 2n for all n >= 0, n ∈ Z.
Solution: We check that it is true for n = 0, 1 and then prove the rest using induction. It holds for n = 0, 1
because 0 < 20 = 1 and 1 < 21 = 2.
Base Case (n = 2): True because 2 < 22 = 4.
Inductive Step: Assume the statement is true for n = k. So k < 2k . Now for n = k + 1 we have
RHS = 2k+1
= 2 ∗ 2k
> 2k
> k + 1 for all k > 1.
This study source was downloaded by 100000850872992 from CourseHero.com on 04-10-2023 23:40:20 GMT -05:00
https://www.coursehero.com/file/11940534/EECS-1028-Final-Exam/
Fall 2011
December 17, 2011
Instructor: S. Datta
1. (2 points) Evaluate the infinite geometric series
9 9 9
+ + + ...
10 100 1000
Note that the left hand side is 0.99 . . .. Use the answer above to fill in the blank below
a 0.9
Solution: This is a geometric series with a = 0.9 and r = 0.1. So the infinite sum is 1−r = 1−0.1 = 1.
0.99 . . . = 1.
2. (2 points) Express the following statement in predicate logic: “given any 2 distinct rational numbers, there
exists a rational number between them in value”.
Solution: Make the domain Q, the set of rational numbers. Then, the given statement is
∀x∀y[(x 6= y) → (∃z(x < z < y) ∨ (x > z > y))].
3. (2 points) Prove that if f : Z+ → Z, f (n) = n2 − 100n then f (n) ∈ Ω(n2 ).
Solution: Note that n2 − 100n ≥ n2 /2 if n ≥ 200. So we use n0 = 200, c = 0.5 in the definition of Ω(n2 )
and thus f (n) ∈ Ω(n2 ).
4. (2 points) What is the negation of ∀x∃yP (x) → Q(y). Your answer should not have negation symbols
before quantifiers and no implication symbols.
Solution: First we rewrite the given statement as ∀x∃y(¬P (x) ∨ Q(y)). Then we can negate this in the
usual way and get
∃x∀y(P (x) ∧ ¬Q(y))
5. (2 points) Write down the function that the following recursive algorithm computes and give a 1-sentence
justification for your answer. Assume that n is a positive integer.
Mystery(n)
1 if n = 1
2 then return 1
3 else return (n + Mystery(n − 1))
Pn n(n+1)
Solution: The program computes i=1 = 2 .
Each recursive call adds the previous number, stopping at 1, so it computes the sum n + (n − 1) + . . . + 2 + 1.
6. (3 points) Prove using induction the inequality n < 2n for all n >= 0, n ∈ Z.
Solution: We check that it is true for n = 0, 1 and then prove the rest using induction. It holds for n = 0, 1
because 0 < 20 = 1 and 1 < 21 = 2.
Base Case (n = 2): True because 2 < 22 = 4.
Inductive Step: Assume the statement is true for n = k. So k < 2k . Now for n = k + 1 we have
RHS = 2k+1
= 2 ∗ 2k
> 2k
> k + 1 for all k > 1.
This study source was downloaded by 100000850872992 from CourseHero.com on 04-10-2023 23:40:20 GMT -05:00
https://www.coursehero.com/file/11940534/EECS-1028-Final-Exam/
