Please print out this problem set and record your answers on the printed copy. answers to this problem set are to be turned in at the box outside by 4: 10 wednesday

1 Strong Induction Recall the principle of strong induction: Principle of Strong Induction. Let(n) be a predicate. If ·P() is true,and for all n, P(O)A P(1)...A P(n) implies P(n+1), then P() is true for all n E N. As an example, let's derive the fundamental theorem of arithmetic

1 The pulverizer We saw in lecture that the greatest common divisor(GCD)of two numbers can be written as a linear combination of them. That is, no matter which pair of integers a and b we are given, there is always a pair of integer coefficients s and t such that

Notes for Recitation 15 Problem 1. Learning to count takes practice! (a)In how many different ways can Blockbuster arrange 64 copies of 13 conversations about one thing, 96 copies of L'Auberge Espagnole and 1 copy of Matrix Revolutions on a shelf? What if they are to be arranged in 5 shelves?

Problem set 2 Solutions Due: Monday, February 14 at 9 PM Problem 1. Use induction to prove that n/n for alln olution. The proof is by induction on n. Let P(n) be the proposition that the equation Base case. P(2 )is true because Inductive step. Assume P(n)is true. Then we can prove P(n +1)is also true as follows

Problem 1. An undirected graph G has width w if the vertices can be arranged in a se- quence V1,2,3,…,Vn such that each vertex v; is joined by an edge to at most w preceding vertices. (Vertex vj precedes if i.) Use induction to prove that every graph with width at most w is (w+1)-colorable

Problem 1. A couple decides to have children until they have both a boy and a girl. What is the expected number of children that they'll end up with? Assume that each child is equally likely to be a boy or a girl and genders are mutually independent Solution. There are many ways to solve

Notes for Recitation 14 Counting Rules Rule 1(Generalized Product Rule). Let be a set of length-k sequences. If there are: n1 possible first entries, n2 possible second entries for each first entry, n3 possible third entries for each combination of first and second entries, etc. then:

Guessing a particular solution. Recall that a general linear recurrence has the form: f(n)=a1f(n-1)+a2f(n-2)+…+aaf(n-d)+g(n) As explained in lecture, one step in solving this recurrence is finding a particular solu- tion; i.e., a function f(n)that satisfies the recurrence, but may not be consistent with the boundary conditions. Here's a recipe to help you guess a particular solution:

Notes for recitation 5 1 Well-ordering principle Every non-empty set of natural numbers has a minimum element Do you believe this statement? Seems obvious, right? Well, it is. But dont fail to realize how tight it is. Crucially, it talks about a non-empty set -otherwise, it would clearly be false. And it also talks about natural