1

Background: I was solving a programming problem and I got to a point where I'm trying to decide whether it is possible to solve a reccurence relation explicitly making the solution complexity better.

I have a set of two reccurence relations: \begin{align}a_{2n+1}&=a_n+2\tag{1}\\a_{2n}&=a_n+1\tag{2}\end{align} with $a_1=1$ and I'm trying to decide whether an explicit form exists.

Thanks.

Galc127
  • 4,451

1 Answers1

3

Write $n$ in a binary number $$n=\overline{c_kc_{k-1}...c_1} \qquad c_i\in\{0,1\}$$ then $$a_n=k-1+\sum_{i=1}^kc_k \tag{1}$$

Indeed, we have $$\begin{align} a(\overline{c_kc_{k-1}...c_1}) &= a(\overline{c_kc_{k-1}...\color{red}{c_2}}) +2\cdot \mathbb{I}_{\{ c_1 =1 \}}++1\cdot \mathbb{I}_{\{ c_1 =0 \}}\\ &=a(\overline{c_kc_{k-1}...\color{red}{c_2}})+c_1+1 \tag{2} \end{align}$$ And $(1)$ can be deduced by recurrence from $(2)$.

Evidently, we need $k$ steps, so $b_n=k = \lceil\log_2(n)\rceil$.

NN2
  • 15,892
  • Sorry for the late comment, could you please elaborate a bit more why this is the form of $a_n$? I thought I understand, but now I'm not sure. Thanks. – Galc127 Dec 07 '22 at 03:49
  • 1
    @Galc127 I detailed how we have the form of $a_n$, I hope the solution is clearer now. – NN2 Dec 07 '22 at 10:27
  • That's great, thanks. How would the answer change for other initial value? – Galc127 Dec 07 '22 at 15:01
  • @Galc127 You meant the initial value of $a_1$? If yes, of course the form of $a_n$ depends on $a_1$. Just notice that $c_k$ is always equal to $1$ and so $$a_n = \sum_{i=1}^{k-1}c_k + (k-1) + a_1 = \sum_{i=1}^{\color{red}{k}}c_k + (k-1) $$ – NN2 Dec 07 '22 at 15:13
  • last thing - if $c_k...c_1$ is the binary representation of n isn't $k=\lceil\log_2 n\rceil$? – Galc127 Dec 07 '22 at 15:47
  • 1
    @Galc127 ah yes, it should be the ceiling, not floor – NN2 Dec 07 '22 at 16:02