CS5002 Discrete Structures Prof. Rachlin Spring 2022 April 6, 2022
Homework #9
Assigned: Wednesday April 6, 2022
Due: Tuesday April 12, 2022 @ 11:59pm ET/Boston −5%: Wednesday April 13, 2022 @ 11:59pm ET/Boston −10%: Thursday April 14, 2022 @ 11:59pm ET/Boston
Copyright By PowCoder代写 加微信 powcoder
Instructions:
• Homework is due on Tuesday at 11:59pm ET/Boston. Homeworks received up to 24 hours late (11:59pm ET on Wednesday) will be penalized 5 percent. Homeworks received up to 48 hours late (11:59pm ET on Thursday) will be penalized 10 percent. NO assignment will be accepted after 48 hours.
• We expect that you will study with friends and fellow students and you are welcome to verbally discuss the problems openly. However, your solution writeup should be the product of your own mind and expressed in your own words. The TAs and I will be available to answer specific questions or address speific points of confusion but we will not verify your answers prior to submission.
• Assignments should be typed using Word or LateX, or hand-written neatly. When submitting to gradescope be sure to indicate the page containing your answer to each problem, so that the TAs don’t have to search for your solution.
• To get full credit, explain your solution and show each step of the solution process! Simply writing down a correct answer will receive little or no credit. We don’t need your scratch work or draft solutions, only your final solution explaining your step-by-step reasoning. Recommendation: try to imagine you need to explain your solution to someone not in this class.
• If you think the TA made a clerical error in grading your assignment, you may submit a regrade request on Gradescope within 1 week of the publication of the grades. After 1 week of publication, ALL GRADES ARE FINAL.
Problem 1 [20 points] Quilting Mathematics
Find a closed form formula for the sequence depicted in the diagram below. For this problem, an denotes the growing number of squares in each figure, so a1 = 1, a2 = 5, a3 = 13, etc.)
You can solve this in at least a couple of different ways.
Method 1: The sequence is an = 1, 5, 13, 25, ….
The first order differences are 4, 8, 12, ….
The second order differences are 4, 4, 4, …. (constant)
So the closed form formula has the form an = an2 + bn + c a1 =a+b+c=1
a2 =4a+2b+c=5
a3 =9a+3b+c=13
3a + b = 4 and 5a + b = 8 so 2a = 4
a = 2, b = −2, c = 1
Soourformulaisan =2n2−2n+1
Method2: Usethemethodofpartialsums. an =1+4+8+12+…+4(n−1) Reversingallbutthefirsttermweget: an =1+4(n−1)+4(n−2)+4(n−3)+…+4 Summing the two expressions together gives: 2an = 2 + 4n + 4n + 4n + …. + 4n Therefore: 2an = 2+4n(n−1) = 4n2 −4n+2
Therefore, an = 2n2 − 2n + 1 (as before).
Problem 2 [25 points]: The Pirates of Penzance
The pirates of Penzance have built a tetrahedral pyramid of cannon balls (i.e, a pyramid with a triangular base). Let C(n) be the total number of cannon balls where n is the height (number of levels) in the pyramid. (C(1)=1, C(2)=4, C(3)=10, etc.). Give a closed-form formula for C(n). What is C(15)? (Hint, to solve this problem you must be very well acquainted, too, with matters mathematical, and understand equations, both the simple and quadratical … or rather cubical!)
n Solution: The number of balls in the base of the pyramid are triangle numbers so C(n) = Ti =
1 + 3 + 6 + 10 + 15 + … The partial sums form a new sequence: C(n) : 1,4,10,20,35… having
constant third order differences, so C(n) = an3 + bn2 + cn + d. Substituting:
C(1) = a + b + c + d = 1
C(2) = 8a + 4b + 2c + d = 4
C(3) = 27a+9b+3c+d = 10
C(4) = 64a + 16b + 4c + d = 20
We have four equations with 4 unknowns. Solving gives a = 16 , b = 21 , c = 13 , d = 0. Therefore: C(n) = 61n3 + 12n2 + 13n. C(15) = 680 cannonballs in a tetrahedral pyramid 15 levels high.
Problem 3 [25 points] Wait, is this Physics 5002?
A rubber ball is dropped from a height of 1 meter. After each bounce it rises to 75% of it’s
previous height as the kinetic and potential energy of the ball disipates in the form of heat with each bounce. Find the total vertical distance (moving both up and down) traveled by the ball before it comes to a rest.
Solution: The ball travels 1m before the first bounce. Between the first and second bounce it travels 0.75m up and then 0.75m down or a total of 2 ∗ 0.75 meters. Between the second and third bounce it travels 2 ∗ (0.75)2 meters and so on.
geometric series sum to infinity
1+2∗0.75+2∗(0.75)2 +2∗(0.75)3 +…
The total distance traveled is =
= 1+1.5∗(1+0.75+0.752 +0.753 +…
= 1 + 1.5 ∗ (1/(1 − 0.75)) = H+1.5∗4
The total distance traveled is 7m.
Problem 4 [30 points] Stairways to Heaven
1. Provebymathematicalinductionthat1+3+5+…+(2n−1)=n2 foralln≥1. Solution:
Basecase(n=1): 2·1−1=1=12
Inductive case: Assume ki=1(2i−1) = k2 for some k ≥ 1. We need to show that (2i−1) =
(k+1)2. But (2i−1)=(2i−1)+2(k+1)−1=k2+2(k+1)−1(bytheinductive
hypothesis.) which simplifies to k2 + 2k + 1 = (k + 1)2. Thus the inductive case holds and by
the principle of mathematical induction, the expression is true for all n ≥ 1.
2. Prove using mathematical induction that 7n − 1 is a multiple of 6 for all n ∈ N.
Basecase: (n=1): 71−1=6=6·m(form=1).
Inductive case: Let k be an arbitrary natural number. Assume that 7k − 1 = 6m for some integer m. Then 7k = 6m+1 and 7k+1 = 7·7k = 7·(6m+1) = 42m+7 (by the inductive hypothesis.) Therefore 7k+1 −1 = 42m+6 = 6·(7m+1) = 6j (where j = 7m+1). So the expression holds for k + 1 and by the principle of mathematical induction, it holds for all n ∈ N.
3. Prove by mathematical induction that 2n < n! for all n ≥ 4. Solution:
Basecase(n=4): 24 =16<24=4!.
Inductive case: Assume 2k < k! for some arbitrary k ≥ 4. We want to show that 2k+1 < (k+1)!. But2k+1 =2·2k <(k+1)·k!(bytheinductivehypothesisandsince2<(k+1) given that k ≥ 4). But (k + 1) · k! = (k + 1)! so the expression holds for the inductive case and by the principle of mathematical induction it must hold for all n ≥ 4.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com