Show that every tree can be colored using two colors.

The rooted Fibonacci trees $T_n$ are defined recursively in the following way. $T_1$ and $T_2$ are both the rooted tree consisting of a single vertex, and for $n=3,4,$dots, the rooted tree $T_n$ is constructed from a root with $T_{n-1}$ as its left subtree and $T_{n-2}$ as its right subtree.