Find recurrence equation and big-oh for the nodes at level n in binary tree
===========================================================================

Recurrence equation:
        /  O(1)                     if n = 1
T(n) = {
        \  O(1) + T(n-1) + T(n-1)   if n > 1

Consider n>1:

T(n) = 1 + T(n-1)          +         T(n-1)
           \_____/                   \_____/
    1 + T(n-2)  +  T(n-2)            1 +   T(n-2)  +  T(n-2)
        \____/     \____/                  \____/     \____/       
 1+T(n-3)+T(n-3)  1+T(n-3)+T(n-3)   1+T(n-3)+T(n-3)  1+T(n-3)+T(n-3) 
         ...

Each time, at each level of replacement, we get a one (really O(1))
appearing a power of 2 times. At the end, T(1) appears 2^(n-1) times.

          0     1     2     3          n-2       n-1
    = 1*(2  +  2  +  2  +  2  + ... + 2    ) +  2

           n-1
        /  ---    \
       |   \    i  |      n                               n
    =  |   /   2   |   = 2  - 1              So T(n) = O(2 ).
        \  ---    /
           i=0