Recurrence Relation

A vending machine accepts only pennies and nickels. a) Find a recurrence relation for the number of ways to deposit n cents where the order in which coins are deposited matters. b) What are the initial conditions for the recurrence? c) Use the recurrence to count the number of ways to deposit 12 cents.

Recurrence Relation

Solve the recurrence relation a(n)=3a(n-1)+10a(n-2) with the initial conditions a(0)=0 and a(1)=2. Solve the recurrence relation a(n)=3a(n-1)+10a(n-2) +12 with the initial conditions a(0)=0 and a(1)=2. For a particular solution, try a(n)=C, a constant.

Equivalence Relation

H is the relation on the set of all people given by H = {(a,b)|a and b are the same height}. Is H an equivalence relation? Explain your answer.

Committee Problem

A committee of size seven is to be selected from a group of ten people. In how many ways can this be done?

Reflexive, Symmetric and/or Transitive

NOTE: I cannot correctly indicate the symbol to show "is a member of" so I have used "E" in it's place. Determine if the relation R on the set of all people is reflexive, symmetric and/or transitive where (x,y) "E" R if and only if x and y live within one mile of each other.

Truth Tables

(a) Use truth tables to prove that an implication is always equivalent to its contrapositive. Site an example where this is so. (b) Use truth tables to prove that an implication may not be equivalent to its converse. Site an example where this is so.

Logical Equivalents

Determine whether (p --> q ) / (p --> r) and p --> (q / r) are logically equivalent. Show all work.

Basic Proof

Prove or disprove the following: If the integer n is divisible by 3, then (nxn) is divisible by 3. Show work.

Proof by Contradiction

Assume that n is a positive integer. Use the proof by contradiction method to prove: (a) If 7n + 4 is an even integer, then n is an even integer. (b) Prove: n is an even integer iff 7n + 4 is an even integer. (Note this is an if and only if (iff) statement.

Computation

Let A = {1,3,5} and B = {3,5}. Compute: (a) A - B (b) A X B (c) A (plus sign with a circle around it) B (d) A ∩ (B - A)