MAT 204 Midterm, Spring 2012
American University of Science and Technology · Discrete Math · 2 pages
Show the text of this exam
. (32 pts) Use mathematical induction to prove that:
1 1 1 1 1 1 1 1
Fy = +...+4——={1 +| —-— |+....+ -—
n+l n+2 2n 2 3 4 2n-1 2n
where n € P
eo 2 92n+1 i¢ divisible by 73 where n € N
ce) 5°-4n-—1=16k where k is an integer and n is a positive integer.
2. (10 pts) Recursively define ag =1, aj =3, a9 =5 and ay, =3a,_7+2ay_3 forn=3
lu
Show a, = 2a,,+(-1)" forn21
3. (10 pts) The Fibonacci numbers /, . /, . f, ..----. are defined by f, = 0, f, =land
f. =F +f. for n2..4.4....
The lucas numbers /, , /, , ....are defined by J, = 2,1], =1,... and 1, =1,_, +1, for
W239, 4.
Show that f, + f,,, =/
whenever 77 is a positive integer.
n+l
4. (6 pts) Establish the following logical equivalence:
[p> (q > r= (paar) -4]
» 4 i pe polar) Vr | pair
0 bw! fae ft 0
0 o | \ l \ " to [
0 0 0 1 Vt] 0
0 i | | \ ) 0 |
to Too | 1 i |
) | | \ ) 0
i [| t [Te | o " | |
| | Filta. =e 4 0
5 (15 pts) Given U= {r, s, t, u, v, w, x, y, Z}, A={r, S, V, X, z},
B= {1, t, u, v, z} and C= { s,t}
a- Find (A @ B) n(B-C)
b- Find the power set of C-B
e- Find (A-B)x (BO C)
d- Find the cardinal of C— B
6 (16 pts) Given the relationship R on set {0,1,2,3,4} such that
R = {(a,b);a+b=2k where k eZ}
a) List the elements of SR
b) List the properties of R
c) Represent the relation using a digraph.
d) Is the relation an equivalence relation? Justify your answer if yes list the
equivalence classes.
(11 pts) A group of 191 students, of which 10 are taking French, business and music;
36 are taking French and Business; 20 are taking French and music, 18 are taking
business and music; 65 are taking French; 76 are taking business and 63 are taking
music.
a- How many are taking French but not business?
b- How many are taking business and neither French nor music?
-
- How many are taking French or Business ( or both)?
d- How many are taking music or French ( or both) but not business?
e- How many are taking none of the three subjects?