DOC PREVIEW
UMD CMSC 250 - Homework #9

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CMSC 250 Homework #9 Fall 20050201 & 0202Due Wed Nov 2 at the beginning of your discussion section.You must write the solutions to the problems single-sided on your own lined paper,with all sheets stapled together, and with all answers written in sequential order oryou will lose points.1. For each of the following statements, either use induction to prove that the statement is true,or give a counterexample with justification to show that it is false.(a) Suppose that the following recurrence relation holdsa1= 1, a2= 0, ∀i ∈ Z≥2, ai= 4ai−1− 4ai−2Prove that ∀n ∈ Z+, an= 2n(1 −n2)Base Case (n = 1, n = 2)n = 1: an= a1= 1 21(1 −12) = 2(12) = 1n = 2: an= a2= 0 22(1 −22) = 2(0) = 0IH(n = i, ∀i ∈ Z, 1 ≤ i ≤ k − 1)ai= 2i(1 −i2)IS(i = k)show: ak= 2k(1 −k2)proof:ak= 4 ak−1− 4ak−2= 4(2k−1(1 −k−12)) − 4(2k−2(1 −k−22))= 4(2k−2(2 − (k − 1)) − 4(2k−3(2 − (k − 2)))= 4(2k−3(2(3 − k) − (4 − k)))= 4(2k−3(2 − k))= 2k−1(2 − k)= 2k(1 −k2)(b) Suppose that the following recurrence relation holdsb1= 4 , b2= 12, ∀i ∈ Z≥2, bi= bi−2+ bi−1Prove that ∀n ∈ Z≥1, 4|bnBase Case (n = 1, n = 2)n = 1 bn= b1= 4 4|4n = 2 bn= b2= 12 4|12IH(n = m, ∀m ∈ Z, 1 ≤ m < k)4|bmIS(n = k)1show: 4|bkproof:bk= bk−2+ bk−14|bk−2therefore ∃r ∈ Z, bk−2= 4r4|bk−1therefore ∃s ∈ Zmb(k − 2) = 4s by def. of dividesbk= 4 r + 4s by substitutionbk= 4(r + s), r + s ∈ Z by closure of Z4|bkby def. of divides(c) Suppose that the following recurrence relation holdsd1=910, d2=1011, ∀k ∈ Z≥3, dk= dk−1· dk−2Prove that ∀n ∈ Z≥1, dn≤ 1Base Case (n = 1, n = 2)n = 1 dn= d1=9100 <910≤ 1n = 2 dn= d2=10110 <1011≤ 1IH(n = i, ∀i ∈ Z, 1 ≤ i < k)di≤ 1IS(n = k)show: dk≤ 1proof:dk= dk−1dk−2dk−1≤ 1/dk−2by IHdk−1≤ 1 from abovedk−1dk−2≤ dk−2by multiplying both sides by dk−2dk−2≤ 1 from abovedk−1dk−2≤ dk−2≤ 1dk≤ 1 by substitution2. Use set notation to answer each of the following questions:(a) Suppose A and B are sets defined a sA = {x ∈ Z|∀k ∈ Z≥1, x = 4k + 1}B = {x ∈ Z|∀k ∈ Z≥1, x = 3k + 5}i. List 1 0 elements of A ∪ Bii. List 10 elements of A ∩ BNote:A = { 5, 9, 13, 17, 21, 25 , 29, 33, 37, 41... }B = {8, 1 1, 14, 17, 20, 23, 26, 29, 32, 35... }A ∩ B = {x ∈ Z|∀k ∈ Z≥1, x = 12k + 17}(b) For each of the following expressions, use a Venn diagram representing the universe U andthe two subsets of that universe A and B. Shade the part of the diagram that correspondsto the set specified by the expression. Note: Acmeans the complement of A.2i. Acii. Bciii. (A ∪ B)civ. Ac∩ Bcv. Ac∪ Bcvi. (A ∩


View Full Document

UMD CMSC 250 - Homework #9

Download Homework #9
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework #9 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework #9 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?