Does this recursive sequence have a closed-form?

Question

Inspired by this simple question at HackerRank, I was wondering if the following sequence has a closed-form:

$$a_0 = 1; \qquad a_n = \begin{cases} a_{n-1} + 1, & \text{if }n\text{ is even} \\[4pt] 2(a_{n-1}), & \text{if }n\text{ is odd} \end{cases}$$

For example, starting at $n=0$, we have:

$1,2,3,6,7,14,\ldots$

Look at this in binary. It will help you understand it better: 1, 10, 11, 110, 111, 1110, 1111, 11110, 11111, 111110, 111111 — Dane Bouchie
– Dane Bouchie, Commented Jun 21, 2014 at 17:35

Omran Kouba · Accepted Answer · 2014-06-21 16:59:35Z

7

$$a_{2n}=2^{n+1}-1,\qquad a_{2n+1}=2a_{2n}=2^{n+2}-2.$$

answered Jun 21, 2014 at 16:59

Omran Kouba

29.2k1 gold badge57 silver badges102 bronze badges

bobbym · Accepted Answer · 2014-06-21 18:10:11Z

5

looks like those numbers are already tabulated,

$$a_n = \frac{(-1)^n}{2}+2^{n/2} \left(1+\sqrt{2}+(-1)^n \left(1-\sqrt{2}\right)\right)-\frac{3}{2}$$

formula by Paul Barry.

answered Jun 21, 2014 at 17:51

bobbym

2,5662 gold badges19 silver badges23 bronze badges

2 Answers 2