Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

2 Answers 2

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.