Macquarie University Department of Mathematics MATH1007 Discrete Mathematics I S2 2020 Assignment 2 Due 8:00 pm, Tuesday 27 October 2020 Assignments are to be submitted electronically via the Assignment 2 page on MATH1007’s iLearn site. This assignment will be marked out of 100. The mark for each question is displayed next to it. This assignment is worth 20% of the overall unit marks. Your work may be hand-written or prepared electronically, and submitted online as a single PDF or Word file. If it is hand-written, take clear scans or photographs of your work and combine these into a single file. Be aware that work that is illegible, because of poor hand-writing say, or due to poor contrast within the scan or photograph, will not be marked. If you find that a question in this assignment confuses you, seek clarification of its meaning by posting a question to the MATH1007 forum. Keep an eye on the forum, as Dom is well known for giving hints to assist with the harder questions. To attain good marks in these questions you must write out your inductive proofs in full and adhere as closely as possible to the proof templates we discussed in the lectures. Solutions without at least a brief explanation, proof or justification will receive no, or only partial, marks. Numbers, induction and recursion ... and a graph or two. 1. In the lectures we proved that the numbers of vertices V and edges E of a tree T satisfied the equation V = E+1. That proof “secretly” used mathematical induction. Write out a proof of that result which explicitly uses one of the induction principles (induction, strong induction or well ordering) discussed in the lectures. [10 marks] Note in your proof you may wish to use the following facts about trees which we proved in the lectures: • Every tree is either the tree with one vertex or it has a leaf vertex, and • The sub-graph obtained by deleting a leaf vertex and its incident edge from a tree is again a tree. 2. Recall that the sequence of Fibonacci numbers fn (n = 0, 1, 2, ...) is defined by the recursive equations f0 = 0 f1 = 1 fn = fn−1 + fn−2 for n ≥ 2. Prove each of the following properties of the Fibonacci numbers using an appropriate induction principle (induction, strong induction or well ordering). a. The inequality fn+1 < (︁ 13 8 )︁n holds for all n ≥ 1. [8 marks] b. Given a fixed number m ≥ 1 the number fmn is divisible by fm for all n ≥ 1. [8 marks] Hint prove this by induction on n. For the inductive step you may assume that the equality fr+m = fr−1fm + frfm+1 holds for all m ≥ 1 and r ≥ 1. c. The equation ∑︁2n+1 i=0 fifi+1 = f 2 2n+2 holds for all natural numbers n ≥ 1. [8 marks] 3. Prove each of the following results using an appropriate induction principle (induction, strong induction or well ordering). ©2020, Department of Mathematics & Statistics, Macquarie University. 1 a. The number 15n+1 + 162n−1 is divisible by 241 for all n ≥ 1. [8 marks] b. For a fixed real number x > 0 the inequality (1 + x)n > 1 + nx+ n(n−1)2 x 2 holds for all n ≥ 3. [8 marks] c. Suppose that a given real number x has the property that x + 1x is an integer, then x n + 1xn is an integer for all natural numbers n. [8 marks] Hint: for the inductive step try expanding the product (xn + 1xn )(x+ 1 x). 4. In this question we study the recursively defined functions f , g and h given by the following defining equations f(0) = −1 base case 0, f(1) = 0 base case 1, and f(n) = n · f(n− 1) + f(n− 2)2 recursive case for n ≥ 2. and g(0,m, r, k) = m base case 0, and g(n,m, r, k) = g(n− 1, r, (k + 2)r +m2, k + 1) recursive case for n ≥ 1. and: h(0,m, r, k) = m base case 0, h(1,m, r, k) = r base case 1, and h(n,m, r, k) = (n+ k) · h(n− 1,m, r, k) + h(n− 2,m, r, k)2 recursive case for n ≥ 2. Note in the following questions computations of the values of recursive functions should be laid out as a sequence of equations, as we have done in the lectures. Each line of that sequence should involve the application of a single defining equation of that function along with any resulting numerical evaluations. In computations of this kind, an expansion step (or just a step) is an application of one of the defining equations of a recursive function to a single instance of that function in an expression. a. Compute the value of f(5). Write out your computation in full. [4 marks] b. Compute the value of g(5,−1, 0, 0). Write out your computation in full. [4 marks] c. How many expansion steps are required to evaluate the expression g(n,m, r, k) for some fixed natural numbers n,m, r and k? Explain your answer. [4 marks] d. Write down a recursive definition for the function c which maps each natural number n to the number of steps c(n) that it takes to evaluate the expression f(n). Explain your answer. [6 marks] Hint: to work out how to define c start by performing the kind of “bullet point” analysis we used in the lectures to show that it takes n + 1 expansion steps to evaluate n!. You can then give that analysis as your explanation of how you came up with your defining equations for c. e. Use strong induction to prove that the function c that you defined in part 4d does indeed have the stated property. That is you should prove that for all natural numbers n it takes c(n) expansion steps to completely evaluate the expression f(n). [8 marks] f. Use strong induction to prove that for all n ≥ 1 and all natural numbers m, r and k the equation h(n,m, r, k) = h(n− 1, r, (k + 2)r +m2, k + 1) holds. [8 marks] g. Explain why the result you proved in part 4f implies that the functions h and g are equal. [2 marks] h. Explain why it is the case that for all natural numbers n we have that f(n) = h(n,−1, 0, 0) = g(n,−1, 0, 0). [2 marks] i. A software engineer needs to evaluate expressions of the form f(n) in her code but, given the analysis above, she opts to use expressions of the form g(n,−1, 0, 0) instead. Explain why it is OK to do that and why you think this engineer might have made that choice. [4 marks] 2 ©2020, Department of Mathematics & Statistics, Macquarie University.
欢迎咨询51作业君
