3

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?

Relure
  • 4,185
Winster
  • 31

3 Answers3

3

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

Joel
  • 16,256
  • 1
    I apologize if the indices get confusing. – Joel Jun 09 '14 at 14:39
  • 1
    I should mention $[k/2]$ is a notation for the largest integer less than $k/2$. Often for integer division in computers, performing the operation $k/2$ yields this quantity. As an example $[1/2]=0$. – Joel Jun 09 '14 at 14:45
  • Thanks for the answer Joel.

    I gather that a good way of approaching such questions seems to be enumerating the sequence first and making observations. Are there any specific approaches that you use when tackling similar problems?

     – Winster Jun 09 '14 at 17:36
  • Honestly my first instinct is to try a generating function first. In that case you don't have to do any pattern matching. Failing that, just look for anything you recognize. In here since we multiplied by 2 frequently, keep an eye out for powers of 2 in the sequence. – Joel Jun 09 '14 at 18:16
3

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

gar
  • 4,948
  • Very nice work with generating functions, gar. – Joel Jun 09 '14 at 15:19
  • Thanks! I think applying g.f. on your recurrences will be easier and neater. – gar Jun 09 '14 at 15:24
  • This is true. Honestly, I tried the gen function first. I stuck with the original formulation and arrived at the identity $$G(x) = 1 + 2x \left( \frac{G(x) - G(-x)}{2} \right) + x \left( \frac{G(x) + G(-x)}{2} \right) + \frac{x}{1-x^2}$$ Rewriting it as you did in the first equation works around this problem. – Joel Jun 09 '14 at 15:30
0

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

Jika
  • 2,970