Finding the explicit notation of $f(n)$, based on it's recursive description. I came across this problem on a HackerRank challenge.
The function $f(n)$ is


*

*$1$ if $n = 0$

*$2f(n - 1)$, if $n$ is odd

*$f(n -1) + 1$, if $n$ is even


I solved the problem using a recursive function and it worked just well. However, I am assuming that a program would work faster if instead of recursion we use an explicit function.
The site gave this solution:
$f(n) = Pow(2, (n+1)/2 + 1) - 1 - (2 \% n)$
Can someone help me arrive at this explicit formation?

To get a closed form, we will first rewrite the recurrence as:
\begin{align*}
  f_n &= 2\, f_{n-2}+1+ \left(n\mod 2\right)
\end{align*}
Next, we will use generating functions, suppose $G(x)= \sum_{n\ge 0}f_n\, x^n$
\begin{align*}
  \sum_{n\ge 2} f_n x^n &= 2\,  \sum_{n\ge 2}f_{n-2}x^n+ \sum_{n\ge 2}x^n+  \sum_{n\ge 2}\left( n\mod 2\right) \\
  G(x)-f_0x^0-f_1x^1 &= 2\,x^2\, G(x) + \frac{x^2}{1-x}+\frac{x^3}{1-x^2} \\
  G(x) &= \frac{1+2\, x}{1-3\, x^2+2\, x^4} \\
  G(x) &= (1+2\, x)\left(\frac{1}{1-\sqrt2 x}+\frac{1}{1+\sqrt2 x}\right)+\frac{1}{2(1+x)}-\frac{3}{2(1-x)}
\end{align*}
Extracting the coefficients $[x^n]$ from each of the partial terms:
\begin{align*}
  \boxed{\displaystyle f_n = 2^{n/2}\left(1+(-1)^n\right)+2^{(n+1)/2}\left(1+(-1)^{n+1}\right)+\frac{(-1)^n-3}{2}}
\end{align*}
Not exactly that formula, but can be modified. And also, that formula needs to be written as:
\begin{align*}
  f(n) = \operatorname{Pow}(2, \operatorname{floor}((n+1)/2) + 1) - 1 - (n\mod 2)
\end{align*}
