Jacobosthal number is defined by $J_n=J_{n-1}+2J_{n-2},J_0=0,J_1=1$. The leading part of the sequence is $0,1,1,3,5,11,21,43,85,\dots\;$. How to show that this number is the number of numbers which is between $2^n$ and $2^{n+1}$ and divisible by $3$?

• Have you tried solving the recurrence relation and finding an explicit formula for $J_n$?
– TMM
Commented Mar 18, 2012 at 16:19
• @TMM, $J_n=\frac{2^n-(-1)^n}{3}$.
– LJR
Commented Mar 18, 2012 at 16:22
• So $$J_n = \begin{cases} \frac{1}{3} (2^n - 1) & n \text{ even;} \\ \frac{1}{3}(2^n + 1) & n \text{ odd.}\end{cases}$$ And how many numbers between $2^n$ and $2^{n+1}$ are divisible by $3$ for $n$ even and $n$ odd?
– TMM
Commented Mar 18, 2012 at 16:25

Find the next number after $2^n$ that is divisible by 3. Do the same thing for $2^{n+1}$. Now, divide their difference by 3 to find the number of multiples of 3.
If $n$ is odd, the numbers divisible by $3$ in our interval are $2^n+1$, $2^n+4$, and so on up to $2^{n+1}-1$. Now we can count them. One has to be a little careful. The answer is $$\frac{1}{3}((2^{n+1}-1)-(2^n+1))+1.$$ (It is easy to forget about the $+1$.)
If $n$ is even, the relevant numbers are $2^n+2$, $2^n+5$, and so on up to $2^{n+1}-2$. Again, we can count them.
Or else note that the recurrence is linear homogeneous with constant coefficients. Solve the recurrence with one of the usual methods. We get $$J_n=\frac{1}{3}\left(2^n-(-1)^n\right).$$ Check that this agrees with the counts obtained earlier.