Recurrence Relation: 1, 2, 4, 6, 10, 14, 20, 26, 36, 46

Question

$$1, 2, 4, 6, 10, 14, 20, 26, 36, 46\ldots$$

Can anyone help me find the recurrence relation for the sequence above. I am unable to figure it out. The pattern begins with the $0$th term. There is a slight pattern, in that from term $1$ to term $2$ and term $2$ to term $3$, it increases by $2$. And from term $3$ to term $4$ and term $4$ to term $5$, it increases by $4$. And from term $5$ to term $6$ and term $6$ to term $7$, it increases by $6$. However, from term $7$ to term $8$ and term $8$ to term $9$, it increases by $10$. This last increase jump is why I am confused.

Any help would be much appreciated

Answer 1

According to OEIS, this is sequence A000123: Number of binary partitions: number of partitions of $2n$ into powers of $2$.

They also provide the following recursive formula:

$a(n)=a(n-1)+a(\left\lfloor\frac{n}{2}\right\rfloor)$

Answer 2

You can construct this row easily when looking a the increases between two terms:

1 2 4 6 10 14 20 26 36 46

+1 +2 +2 +4 +4 +6 +6 +10 +10

The increases show the same behavior as the original row (except that each increase occurs twice and the first +1 is missing, which leads me to assume that a 0 might be missing at the start).

Thus, the next elements are:

60, 74, 94, 114, ...