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 Mar 18 '12 at 16:19
@TMM, $J_n=\frac{2^n-(-1)^n}{3}$. –  LJR Mar 18 '12 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 Mar 18 '12 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.

Now verify that these counts satisfy the recurrence and the initial conditions.

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.

-