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

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

• Hint: Look at your increasings again. Do you find the sequence 1, 2, 4, 6, 10 elsewhere? (As a side note, I would assume that there is a term 0 missing in front of the row.) Commented Feb 22, 2017 at 9:22
• See here: oeis.org/…
– user371838
Commented Feb 22, 2017 at 9:25
• Question: Are you sure the 0th term is 1. that seems to be the odd man out of this recursive sequence. Commented Feb 22, 2017 at 9:26
• With so little terms (noting that the first order differences seem to come in pairs), any answer is risky. We need more context. Where is this coming from ?
– user65203
Commented Feb 22, 2017 at 9:28

## 2 Answers

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

• I'm not sure that the person knows what the floor function is. but yes this is correct. Commented Feb 22, 2017 at 9:32
• @Sentinel135 If he doesn't he will ask again I suppose ;-) Commented Feb 22, 2017 at 10:56

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, ...