Working through a problems practice coloring, I have found a problem that has me stumped. The problem states:
For $n \in \mathbb{R}_{>o}$ the binary tree is defined recursively as follows. The tree $T_1$ consists of a single vertex. For $n > 1$ the tree $T_n$ consists of two copies of $T_{n-1}$ and an additional new root vertex that is adjacent to the roots of the two copies. Find a formula for the number of 3 colorings of $T_n$ and prove it.
Here is a diagram of the tree.
I am having trouble with the recursive definition of the tree. Is the new vertex generated each time we move another level or is it just the one root? Any help would be appreciated.
Hint:
The tree $T_1$ is a single vertex $\bullet$, tree $T_2$ is $\bullet \to \bullet \gets \bullet$, while tree $T_3$ is $$\begin{array}{c} &&&&\bullet\\ &&&\swarrow&&\searrow \\ &&\bullet&&&&\bullet \\ &\swarrow&\downarrow&&&&\downarrow&\searrow \\ \bullet&&\bullet&&&&\bullet&&\bullet \end{array}$$ The $n$-th tree has $2^n-1$ vertices.
Let $g(n)$ be the number of 3-colorings of $T_n$ when the color of the root is restricted to two colors only, then
\begin{align} g(n) &= (\text{colorings of the root}) \\ &\quad\text{times}\ (\text{colorings of the left subtree}) \\ &\quad\text{times}\ (\text{colorings of the right subtree}) \\ & = 2 \cdot g(n-1) \cdot g(n-1) \\ \end{align}
I hope this helps $\ddot\smile$