Discrete Mathematics I
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]
