Sequences & Big-O
Let an = 3an-1 – an-2 , a0 = 1, and a1 = 1. What is a5?
a5 = 34
What is the quotient and remainder when I divide -136 by 21?
q = -7, r = 11
Describe the difference between PMI (principle of mathematical induction) and strong induction. Give an example of a scenario in which you would want to 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 i<=k.
How many 6-element DNA sequences… (note: DNA elements can be either A, T, C, or G only)
Do not contain A?
End with CG?
1. 36 = 729
2. 44 = 256
How many numbers must be selected from the set
{1, 2, 3, 4, 5, 6, 7, 8} to guarantee that at least one pair of the selected numbers sums to 9?
5
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).
Evaluate the following:
(1011)2 * (1110)2
(1011)2 * (1110)2 = (1001 1010)2
Suppose we want to prove by PMI that 6 divides n3−n whenever n is a nonnegative integer.
Complete the base case and inductive assumption.
Base case: n=1; 13–1 = 0, 6*0 = 0. Thus by definition, 0 is divisible by 6.
Inductive assumption: Assume for n=k there exists an integer a such that k3–k=6a.
How many numbers between 101 and 901 (inclusive of endpoints) are divisible by 6?
900-102/6 + 1= 134
What is the coefficient of x42y9 in (x + y)51?
Just set the problem up, do not worry about solving it.
C(51, 9)
Determine if an = 3n is a solution to the recursively defined sequence an = 5an-1 – 6an-2.
Must show your work and defend your answer to get points.
Yes! Plug in 3n for an in recursive definition, then simplify to see if we can get back to 3n.
Are 8924 and 272 relatively prime? If not, find their GCD.
gcd(8924, 272) = 4.
Suppose we want to prove by PMI that the following is true for all integers n>0. Complete the inductive assumption and inductive step (skip base case).
31+32+...+3n = (3n+1–3)/2.
Inductive assumption: Assume for n=k that 3+32+...+3k=(3k+1–3)/2 is true.
Inductive step: Show for n=k+1 that 3+32+...+3k+3k+1=(3k+2–3)/2 is true.
3+32+...+3k+3k+1 = (3k+1–3)/2 + 3k+1 = (3k+1–3)/2 + (2 *3k+1)/2 = (3*3k+1–3)/2 = (3k+2–3)/2. Proved by PMI.
How many passwords of only made up of 8 lowercase english alphabet letters either start with "a" or end with "xy" if letters can be repeated.
Do not simplify, just set the problem up!
267 + 266 – 265
My sock drawer contains 14 pairs of socks. 6 of these pairs are white, 4 pairs are black, and the remaining pairs have cats on them. None of my socks are paired in the drawer.
How many socks do I have to take out to ensure I get at least two cat socks?
22
Find a solution (explicit formula) to the recurrence relation an=2n * an-1 when a0 = 1.
an = 2n * n!
Convert (3672)8 to decimal.
(1978)10
Prove that for all n>0,
1*1! + 2*2! +...+ n*n! = (n+1)! – 1
BC: n=1: LHS: 1*1! = 1, RHS: (1+1)!–1=2–1=1, LHS=1=RHS.
IA: Assume for n=k that 1*1! + 2*2! +...+ k*k! = (k+1)! – 1 is true.
IS: Show that for n=k+1, 1*1! + 2*2! +...+ k*k! + (k+1)(k+1)! ?= (k+2)! – 1
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?
C(1, 1) * P(99, 3) = 941,094
Imagine two competing genetic research labs, "Alpha" and "Omega," that are mapping DNA. Lab Alpha is working on a project to create a library of all possible valid, functional proteins. A protein is just a finite-length string made from a set of 20 possible amino acids. Lab Alpha wants to create a database and assign a unique identifying integer to every single possible finite-length protein, even the ones that are trillions of amino acids long. Lab Omega is working on a different project. They are creating a "genetic marker" by measuring the exact ratio of two specific enzymes in a cell. This ratio can be any real number between 0 and 1 . Lab Omega wants to create a database and assign a unique identifying integer to every single possible ratio. Which lab will fail? Why?
Lab Omega! The set of all possible ratios between 0 and 1 is uncountably infinite. It is impossible to create a complete, ordered list of all real numbers. This set has a "larger" size of infinity than the integers.
Find the closest big-O bound for f. Prove your solution is correct by finding c and k.
f(n) = (2n3 + n)(3n3 + 4n4 - n)
f(n) is O(n7) for...
c = 11 and k = 6 OR c = 19 and k = 1.
Notice c and k are not unique.
Find (87 mod 15)4 mod 11.
Use mod theorem & show your work!
5
Prove by strong induction that for all integers n>7, n can be expressed as a sum of 3s and 5s.
Base case: n=8=3+5, n=9=3*3, and n=10=5*2
Inductive assumption: Assume for 8<= i <=k that i can be represented by a sum of 3s and 5s s.t. i=3a+5b where a and b are integers.
Inductive step: show the statement is true for n=k+1.
n = k+1 = k+1+2–2 = (k–2) + 3 = 3a+5b+3 = 3(a+1)+5b. a and b are integers, so a+1 is also an integer.
There are 52 cards in a deck. How many ways can I get a seven-card hand so that I have exactly three kings and exactly two hearts?
You do not need to evaluate, just set the problem up!
C(3, 3) * C(12, 2) * C(36, 2) + C(1, 1) * C(3, 2) * C(12, 1) * C(36, 3).
What is the coefficient of x14 in (5 – 2x2)10?
C(10, 7) * 53 * (-2)7