Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Homework 2
Type-set solutions are preferred. Remember that written homework solutions must be type-set
to be eligible for electronic submission. If you submit a hand-written solution, please make an
effort to use neat, clean handwriting. Hand-written homework solutions must physically submitted
in-person. See syllabus for more details regarding this policy.
Reminder: CSE 491 adheres to Michigan State University’s policies on academic integrity. No
collaboration is allowed on homeworks, and all work must be your own.
1. (10 points) The unrooted version of a rooted leaf-labeled binary tree can be obtained by
simply ignoring edge directionality, deleting the root, and then “connecting” its two incident
edges.
Equivalently, an unrooted leaf-labeled binary tree is an undirected graph G = (V, E) where
G is connected, acyclic, all nodes v ∈ V have degree of either 1 (i.e., leaf nodes) or 3 (i.e.,
internal nodes), and all leaf nodes have distinct labels. Recall that the degree of a node in
an undirected graph is defined as the number of edges incident upon it.
For example, see Figure 1 which shows three distinct unrooted leaf-labeled binary trees. These
are the only possible distinct unrooted leaf-labeled binary trees with four taxa.
Using induction, prove that the number of distinct unrooted leaf-labeled binary trees on n
taxa is (2n 5)!!.
Figure 1: These are the only possible distinct unrooted leaf-labeled binary trees with four taxa.
(5 points) Without using induction, prove that the number of distinct unrooted leaf-labeled
binary trees on n taxa is (2n 5)!!.
(Hint: you can make use of the fact that the number of distinct rooted leaf-labeled binary
trees on n taxa is (2n 3)!!, as we proved in class.)
2. (5 points) Let i be a natural number. Let T be the set of rooted binary trees which have
n = 2i
leaves. Let X T be the subset of such trees having maximal height. What property
(or properties) do the trees in X have in common? Prove that your answer is correct.
(5 points) Let Y T be the subset of such trees having minimal height. What property (or
properties) do the trees in Y have in common? Prove that your answer is correct.
1
3. Optional bonus problem (+10 extra credit points):
Recall that the nth Fibonacci number can be defined using a recursive function f:
f(0) = 1
f(1) = 1
f(n) = f(n1) + f(n2) where n is a natural number greater than 1
Also recall that the golden ratio constant is defined to be, and the complement of
φ is defined to be ψ = 1
Prove that f can be equivalently expressed in the following non-recursive form:
f(n) = φ
where n is a natural number