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?

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}$$
