Trying to solve this task by solving the recurrence https://www.hackerrank.com/challenges/utopian-tree/problem
g(0)=1
g(n)=2*g(n-1), if n is odd
g(n)=g(n-1)+1, if n is even
I tried to use plug and chug method to expand the pattern, but I failed. Either with the generating function. Could you please drop a hint for me?
The trick, for either method, is to start by combining the relations to get a spearate formula for odd (or for even) indices.
Thus: $$g_{2n+2} = 2g_{2n+1} = 2(g_{2n}+1) = 2g_{2n}+2$$ Let $h_n \equiv g(2n)$, then $h_{n+1} = 2h_n + 2$. To use the method of generating functions we need to put this into a generic form, good for all $n$ assuming $h_{-|k|} = 0$, namely $$ h_{n+1} = 2h_n + 2 -[n=0] $$ Now multiply by $z^n$ and sum: $$ \sum h_{n+1}z^n = 2\sum h_n z^n + 2\sum z^n - 1 \\ \frac1z \sum h_{n+1}z^{n+1} = 2 H(z) +2\frac1{1-z}-1\\ \frac1z H(z) = 2 H(z) +2\frac1{1-z}-1 \\ H(z) = \frac{z(1+z)}{(z-1)(2z-1)} $$ and the generating function for $g_z$ is given by $G[z] = H(z^2)$.
To solve via "plug and chug," you start from $$h_{n+1} = 2h_n + 2$$ and notice that $h_k$ will roughly double each iteration, so define $m_k \equiv 2^{-k} h_k $ (with $m_0 = 1$) to get $$ 2^{k+1}m_{k+1} = 2^{k+1}m_k +2 \\ m_{k+1} = m_k + 2\cdot 2^{-(k+1)} = =m_k+2^{-k} \\ m_k = 1+\sum_{n=0}^k 2^{-n} = 3 - 2^{-k} \\ h_k = 3\cdot 2^k -2 $$ which means that $$ g_{2n} = 3\cdot 2^{n} -2 $$ and $$ g_{2n+1} = 3\cdot 2^{n} -1 $$