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?
 A: First I would start by writing out the sequence: $$f(0)=1, f(1) = 2, f(2) = 3, f(3) = 6, f(4) = 7, f(5) = 14, f(6) = 15, ...$$
Now notice that $f(0) = 2 - 1 = 2^{0+1} - 1$, $f(2) = 4-1 = 2^{1+1} - 1$, $f(4) = 8-1 = 2^{2+1} - 1$, and $f(6) = 16 - 1 = 2^{3+1}-1$. So we conjecture that $$f(2n) = 2^{n+1} - 1$$
Now it is also clear that $$f(2n-1) = 2f(2n-2) = 2^{n+1}-2$$

From here we just need to verify the conjectures with induction. We see that it certainly holds for $f(k)$ up to $k=6$. Now suppose it holds for $f(k)$ where $k=2n$.
Consider $$f(k+1) = f(2n+1) = 2f(2n) = 2(2^{n+1} - 1) = 2^{n+2} - 2$$ so we have verified this for the odd case.
Now if the conjecture holds for $f(k)$ where $k=2n+1$ then we have $$f(k+1) = f(2n+2) = f(2n+1) + 1 = 2^{n+2}-2+1 = 2^{n+2} - 1$$
Thus we see by induction that $$f(2n) = 2^{n+1}-1$$ and $$f(2n+1) = 2^{n+2} - 2$$ as we conjectured.

Now if you want this in one equation, we write $$f(k) = 2^{[(k+1)/2]+1} - 1.5 + (0.5)(-1)^{k}$$
A: 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*}
A: I tried to solve it as follow:
For $n$ odd, let $n=2k+1$ for some $k$. Then:
$$
f_n=f_{2k+1}=2f_{2k}=2\left(f_{2k-1}+1\right)=2f_{2k-1}+2=2^2f_{2k-2}+2=\cdots
$$
I continue until $f_0$. And I did the same thing for $n$ even. So I get the following:
Let, $n\div2=p$ and $n\mod2=q=\begin{cases}0\, \text{if}\, n\, \text{is even}\\1\,\text{ else}\end{cases}$, then: $n=2\times p+q$
$$
f_n=
\begin{cases}
\sum\limits_{i=1}^{p+q}2^i,\text{if }n\, \text{is odd}\\
1+2^{p}+\sum\limits_{i=1}^{p-1}2^i,\text{if }n\, \text{is even}
\end{cases}.
$$
