-1
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Thern
    Feb 22, 2017 at 9:22
  • $\begingroup$ See here: oeis.org/… $\endgroup$
    – user371838
    Feb 22, 2017 at 9:25
  • $\begingroup$ Question: Are you sure the 0th term is 1. that seems to be the odd man out of this recursive sequence. $\endgroup$ Feb 22, 2017 at 9:26
  • 1
    $\begingroup$ 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 ? $\endgroup$
    – user65203
    Feb 22, 2017 at 9:28

2 Answers 2

3
$\begingroup$

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

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

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .