Functions & Sequences
What is a sequence? Give an example of an explicitly defined sequence.
A sequence is a function from the set of natural numbers (sometimes including 0) to another set.
Example: {an}=n
Suppose we have two known integers, a and b. Explain the following division definition:
a = b*x + y
Specifically, what do the variables x and y represent?
x is the quotient and y is the remainder, such that 0<=y<b.
What are the three necessary components for all types of induction proofs? Describe each component.
Base case: Prove the statement is true for the smallest value of n (usually n=0 or 1, but subject to change).
Inductive assumption: Assume the statement is true for n=k.
Inductive step: Show the statement is true for n=k+1.
How many 6-element DNA sequences…
Do not contain A?
End with CG?
1. 36 = 729
2. 44 = 256
What does it mean if we say f(x) is O(g(x)) for constants c and k?
c*g(x) is bigger than f(x) for all x >= k.
Find the inverse function of f(x) = x3+1. Prove your solution is correct.
f-1(x) = (x – 1)1/3
f(f-1(x)) = x and f-1(f(x)) = x.
What does (761)8 + (1001 0111)2 evaluate to in base 2?
(10 1000 1000)2
Describe the difference between PMI (principle of mathematical induction) and strong induction. Give an example of a scenario in which you would use strong induction over PMI.
For PMI, in our inductive assumption, we assume the statement is true for n=k. For strong induction, in our inductive assumption, we assume the statement is true for n<=k.
One hundred tickets, numbered 1, 2, 3, ... , 100, are sold to 100 different people for a drawing. Four different prizes are awarded, including a grand prize. How many ways are there to award the prizes if…
the person holding ticket 42 wins the grand prize?
the person holding ticket 42 wins one of the prizes?
the person holding ticket 42 does not win a prize?
1. the person holding ticket 42 wins the grand prize P(99, 3) = 941,094
2. the person holding ticket 42 wins one of the prizes? C(4, 1) * P(99, 3) = 3,764,376
3. the person holding ticket 42 does not win a prize P(99, 4) = 90,345,024
What is the coefficient of x42 in (x – 2)51?
Just set the problem up, do not worry about solving it.
C(51, 9) * (-2)9
Find a solution to the recurrence relation an=n*an–1.
5 * n!
Evaluate the following:
(-136 mod 21 + 163 mod 21) mod 5
(11 + 16) mod 5 = 27 mod 5 = 2
Prove by PMI that for all integers n>0, 31+32+...+3n = (3n+1–3)/2.
Base case: n=1; LHS=31=3 and RHS=(32–3)/2=6/2=3.
Inductive assumption: Assume for n=k that 3+32+...+3k=(3k+1–3)/2 is true.
Inductive step: Show for n=k+1 the statement is true.
How many passwords of only made up of 8 lowercase english alphabet letters either start with "a" or end with "xy"?
Just set the problem up!
726 + 626 – 526
If I want to guarantee that at least 10 students in a class share the same birthday month, how many students must be enrolled in the course?
109 students.
Determine if the sequence an=(-n)+2is a solution of the recurrence relation an = an–1 + 2an–2 + 2n − 9. If you answer yes, prove the sequence is, in fact, a solution of the recurrence relation.
Yes, an=(-n)+2 is a solution to the recurrence relation.
Use Euclid's algorithm to determine gcd(8924, 272).
gcd(8924, 272) = 4.
Prove by PMI that 6 divides n3−n whenever n is a nonnegative integer.
Hint: You may use the fact that the product of an even number and an odd number is even without proof.
Base case: n=1; 13–1 = 0, 6*0 = 0.
Inductive assumption: Assume for n=k that k3–k=6a, where a is an integer.
Inductive step: Show the statement is true for n=k+1.
I have 5 history books, 4 math books, and 8 novels. I want to put exactly 3 history books, 4 math books, and 5 novels on a shelf. I also want to keep the genres together on the shelf. How many ways can the shelf be arranged?*
*You do not need to evaluate, just set the problem up!
C(5, 3) * 3! * C(4, 4) * 4! * C(8, 5) * 5! * 3!
Find the closest big-O bound for f(x) = 2x(3+x2). You do not need to find constants c and k (but you can if you want).
f(x) is O(x3).
Determine if the following function is a bijection. If your answer is yes, prove it.
Let f be defined on the set of all real numbers. Then, f(x) = 2x+5.
The function is bijective!
Multiply the following integers in base 16. Then, convert your solution to base 10.
(A7F4)16 * (13)16
(A7F4)16 * (13)16 = (C771C)16 = (816 924)10
Prove by strong induction that for all integers n>5, n can be expressed as a sum of 2s and 3s.
Base case: n=6 and n=7
Inductive assumption: Assume for n<=k that k can be represented by a sum of 2s and 3s s.t. k=2a+3b where a and b are integers.
Inductive step: show the statement is true for n=k+1.
n = k+1 = k–1+1+1 = (k–1) + 2 = 2a+3b+2 = 2(a+1)+3b. a and b are integers, so a+1 is also an integer.
Thus, for n>5, n can be represented by a sum of 2s and 3s. Proved by strong induction.
There are 52 cards in a deck. How many ways can I get a six-card hand so that I have exactly two aces and exactly 3 spades?
*You do not need to evaluate, just set the problem up!
C(3, 2) * C(12, 3) * C(36, 1) + C(3, 1) * C(12, 3) * C(36, 1)
My sock drawer contains 14 pairs of socks. 6 of these pairs are white, 4 pairs are black, and the remaining pairs are blue. None of my socks are paired in the drawer.
1. How many socks do I have to take out to ensure I get at least two that match?
2. How many socks do I have to take out to ensure I get at least two blue socks?
1. 4
2. 22