About Warm-ups Problems News

Exercise R

Posted 05/06/2015
Refresh the webpage if formulas are not shown correctly.
--------------------------
Previous    Next
--------------------------

Suppose `T_n` is a perfect binary tree of height `n`, that is each node has exactly two children except that nodes at top level have no children. `T_3` and `T_4` are drawn in the following figure .



An apple tree of height `n` is a prefect binary tree of height `n` where apples may grow at any node except the root and no apples are grown at adjacent nodes. For example, the following figure shows an apple tree of height `3` and an apple tree of height `4`. Nodes with apples are in red.



`a(n)` is the number of distinct apple trees of height `n`.

For example, `a(1)=1`, `a(2)=4`, `a(3)=25`.

Find `a(n)`.