Jacobsthal sequence

The Jacobsthal sequence is an additive sequence similar to the Fibonacci sequence, defined by the recurrence relation $J_n=J_{n-1}+2J_{n-2}$, with initial terms $J_0=0$ and $J_1=1$. A number in the sequence is called a Jacobsthal number. The first few are 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, etc., listed in A001045 of Sloane’s OEIS.

The $n$th Jacobsthal number is the numerator of the alternating sum

$$\sum _{i=1}^n{(-1)}^{i-1}\frac{1}{2^i}$$

(the denominators are powers of two). This suggests a closed form: by putting the series solution over a common denominator and summing the geometric series in the numerator, we obtain two equations, one for even-indexed terms of the sequence,

$$J_{2n}=\frac{2^{2n}-1}{3}$$

and the other one for the odd-indexed terms,

$$J_{2n+1}=\frac{2^{2n+1}-2}{3}+1.$$

These equations can be further generalized to

$$J_n=\frac{{(-1)}^{n-1}+2^n}{3}.$$

The Jacobsthal numbers are named after the German mathematician Ernst Jacobsthal.