RECURSION

int utopianTree(int n) { if(n==0) return 1; if(n%2==0) return 1 + utopianTree(n-1); return 2 * utopianTree(n-1); }

c#

 int height = 1;
        for (int i = 1; i <= n; i++)
        {
            if (i % 2 == 1) // nieparzyste
            {
                height *= 2;
            }
            else // parzyste
            {
                height += 1;
            }
        }
        return height;

class Result {

/*
 * Complete the 'utopianTree' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts INTEGER n as parameter.
 */

public static int utopianTree(int n) {
// Write your code here

ArrayList arr=new ArrayList<Integer>();


int count=0;

for(int i=0;i<=n;i++)
{
    if(i%2==0)
    {
        count+=1;
        arr.add(i, count);
    }
    else
    {
        count=count*2;
        arr.add(i, count);
    }
}

int wawa=(int)arr.get(n);
return wawa;


}

}

Simple no brainer Python 3 solution:

def utopianTree(n):
    count = 0
    for i in range(n+1):
        if i == 0:
           count += 1
        elif i % 2 == 0:
            count += 1
        else:
            count *= 2
    return count