Finding a recurrence relation

Question

I need to find a recurrence relation or an exact formula to the sequence $$1,2,4,8,12,16,24,32,40,48,64,80,96,112,128,160,192,224,256,288,\ldots$$ Well, considering $a_0=1$, $a_1=2$ and $a_2=4$, the terms $a_n$ for $n\geq3$ is obtained by adding a power of $2$. In fact the sequence is: $$1\xrightarrow{+1}2\xrightarrow{+2}4\xrightarrow{+4}8\xrightarrow{+4}12\xrightarrow{+4}16\xrightarrow{+8}24\xrightarrow{+8}32\xrightarrow{+8}40\xrightarrow{+8}48\xrightarrow{+16}64\xrightarrow{+16}80\xrightarrow{+16}96\xrightarrow{+16}112\xrightarrow{+16}128\xrightarrow{+32}160\ldots$$ and we will have $5+1$ addition of $32=2^5$ and then $6+1$ addition of $64=2^6$ and so on.

Any, solutions, suggestions,... please.

Answer 1

To compute the $n^{th}$ term, find $k$ such that $\frac{k(k-1)}{2} \leq n \leq \frac{k(k+1)}{2}$. Then:

$x(n) = x(n-1) + 2^{k-1}$.

For example, if $n=9$, $k=4$ and $x(9) = x(8) + 8$.

Let's first look at the roots of $k^2-k -2n=0$. They are given by $r_1 = \frac{1-\sqrt{1+8n}}{2}$ and $r_2 = \frac{1+\sqrt{1+8n}}{2}$.

The inequality $\frac{k(k-1)}{2} \leq n$ implies $k^2-k-2n \leq 0$, i.e. $(k-r_1)(k-r_2) \leq 0$, which is true when $r_1 \leq k \leq r_2$. Since $k >0$ and $r_1<0$, the condition reduces to $0 < k \leq r_2$. For example, when $n=9$, $0 < k \leq 4.77$.

Now let's look a the roots of $k^2+k-2n=0$. They are given by $r_3 = \frac{-1-\sqrt{1+8n}}{2}$ and $r_4 = \frac{-1+\sqrt{1+8n}}{2}$.

The inequality $n \leq \frac{k(k+1)}{2}$ implies $k^2+k-2n \geq 0$, i.e. $(k-r_3)(k-r_4) \geq 0$, which is true when $k \leq r_3$ or $k \geq r_4$. Since $k>0$, this reduces to $k \geq r_4$. For example, when $n=9$, $k \geq 3.77$.

Combining the two, we have:

$\frac{-1+\sqrt{1+8n}}{2} \leq k \leq \frac{1+\sqrt{1+8n}}{2}$.

One may be able to write this as $k = \text{round} \left( \frac{\sqrt{1+8n}}{2}\right)$ and $x(n) = x(n-1) + 2^{k-1}$. The ambiguity when $8n+1$ is a perfect square needs to be resolved (e.g. when $n=10$).