Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.