MATH 3339 EXAM QUESTIONS AND
ANSWERS 100% CORRECT
44x=10mod74 - ANSWER-linear congruence
x=12+37k
linear congruence - ANSWER-Step 1: find gcd
Step 2: Ext eucl algo
Mathematical Induction - ANSWER-Base Case: show that p(1) is true
Inductive step: prove P(k) then P(k+1)
Conclusion: p(n) is true
s 5. By using mathematical induction, prove that for every positive integer n, Xn i=1 i
· 2 i = (n − 1)2n+1 + 2. - ANSWER-k*2^(k+2)+2
Give a recursive definition of the set of bit strings that have "odd" length. For
example, 1 or 001 have odd length, but 00 or 1011 have even length. - ANSWER-
Base step: 1=s, o=s
inductive step: if w=s then w10,w01,w00,w11=s
Give a recursive definition of the set of all even positive integers not divisible by 4 -
ANSWER-Base step: 1,3,5,7=s
Recursive step: if x=s, then (x+8
Pigeonhole - ANSWER-ceiling function n/3=24 n=3*23+1
Generalized Pigeonhole Principle - ANSWER-ceiling function 677/38=18
Combination - ANSWER-C (n, r ) = ( n r )= n!/ r !(n − r )!
Permutation - ANSWER-P(n, r ) = n!/ (n − r )!
Among 200 people, find the least number of them who were born in the same week
of the year. - ANSWER-(200/52)+1
A professor packs her collection of 30 issues of a mathematics journal in Boxes
numbered A, B, C. She puts 5 issues in Box A, 10 issues in Box B and 15 issues in
Box C. In how many ways can she distribute these journals? - ANSWER-
30c5(25c10)(15c15)
1. Let a0= 0, a1= 1, and an= 5an−1− 6an−2 for n ≥ 2. Prove by strong induction that
an = 3n − 2 n , for all n ≥ 0. - ANSWER-
How many positive integers not exceeding 300, are divisible by 5 or 7? - ANSWER-
ANSWERS 100% CORRECT
44x=10mod74 - ANSWER-linear congruence
x=12+37k
linear congruence - ANSWER-Step 1: find gcd
Step 2: Ext eucl algo
Mathematical Induction - ANSWER-Base Case: show that p(1) is true
Inductive step: prove P(k) then P(k+1)
Conclusion: p(n) is true
s 5. By using mathematical induction, prove that for every positive integer n, Xn i=1 i
· 2 i = (n − 1)2n+1 + 2. - ANSWER-k*2^(k+2)+2
Give a recursive definition of the set of bit strings that have "odd" length. For
example, 1 or 001 have odd length, but 00 or 1011 have even length. - ANSWER-
Base step: 1=s, o=s
inductive step: if w=s then w10,w01,w00,w11=s
Give a recursive definition of the set of all even positive integers not divisible by 4 -
ANSWER-Base step: 1,3,5,7=s
Recursive step: if x=s, then (x+8
Pigeonhole - ANSWER-ceiling function n/3=24 n=3*23+1
Generalized Pigeonhole Principle - ANSWER-ceiling function 677/38=18
Combination - ANSWER-C (n, r ) = ( n r )= n!/ r !(n − r )!
Permutation - ANSWER-P(n, r ) = n!/ (n − r )!
Among 200 people, find the least number of them who were born in the same week
of the year. - ANSWER-(200/52)+1
A professor packs her collection of 30 issues of a mathematics journal in Boxes
numbered A, B, C. She puts 5 issues in Box A, 10 issues in Box B and 15 issues in
Box C. In how many ways can she distribute these journals? - ANSWER-
30c5(25c10)(15c15)
1. Let a0= 0, a1= 1, and an= 5an−1− 6an−2 for n ≥ 2. Prove by strong induction that
an = 3n − 2 n , for all n ≥ 0. - ANSWER-
How many positive integers not exceeding 300, are divisible by 5 or 7? - ANSWER-
