The statement is true. Write $F_n$ for the $n$-th Fibonacci (my indexing starts at $(F_0, F_1, F_2, F_3, \dots) = (0,1,1,2,\dots)$). We are being asked to show that
$$\frac{1}{F_{j+1}} > \sum_{m=F_{j}+1}^{F_{j+1}} \frac{1}{m} - \sum_{m=F_{j-1}+1}^{F_{j}} \frac{1}{m} > 0\ \mbox{for}\ j \geq 6.$$
Computer computations easily check this for $6 \leq j \leq 20$, so we only need to check large $j$.

We know that
$$H(n) = \log n + \gamma + \frac{1}{2n} + O(1/n^2)$$
where the constant in the $O( \ )$ can be made explicit -- something like $1/12$.
So
$$\sum_{m=B+1}^C \frac{1}{m} - \sum_{m=A+1}^B \frac{1}{m} = \log \frac{AC}{B^2} + \frac{1}{2} \left(\frac{1}{A}-\frac{2}{B}+\frac{1}{C} \right) + O(1/A^2)$$
where the constant in the $O( \ )$ is something like $1/3$.

Now, $F_{j-1} F_{j+1} = F_j^2 \pm 1$. So
$$\log \frac{F_{j-1} F_{j+1}}{F_j^2} = \log \left( 1 \pm \frac{1}{F_j^2} \right) = O(1/F_j^2).$$
So, up to terms with error $O(1/F_j^2)$ and a fairly small constant in the $O( \ )$, we are being asked to show that
$$\frac{1}{F_{j+1}} > \frac{1}{2} \left( \frac{1}{F_{j+1}} - \frac{2}{F_j} + \frac{1}{F_{j-1}} \right) > 0.$$

Set $\tau = \frac{1+\sqrt{5}}{2}$, and recall that $F_j = \frac{\tau^j}{\sqrt{5}} + O(\tau^{-j})$. Then, up to errors of $O(\tau^{-3j}) = O(1/F_j^3)$, this turns into the inequalities
$$\frac{1}{\tau^2} > \frac{1}{2} \left( 1 - \frac{2}{\tau} + \frac{1}{\tau^2} \right) > 0.$$
The latter is obviously true; the former can be checked by calculation.

It looks like the same analysis should apply sufficiently far out any linear recursion with solution of the form $G_j = c_1 \theta_1^j + \sum_{r=2}^s c_r \theta_r^j$ where $1 < \theta_1 < 1+\sqrt{2}$ and $|\theta_r|<1$ for $r>1$. (So $\theta_1$ should be a Pisot number.) The inequality $|\theta_r|<1$ makes $\log \frac{G_{j+1} G_{j-1}}{G_j^2} \approx \frac{\max_{r \geq 2} |\theta_r|^j \theta_1^j}{\theta_1^{2j}}$ be much less than $1/G_j \approx 1/\theta_1^j$. The inequality $\theta_1 < 1+\sqrt{2}$ makes $1/\theta^2 > (1/2)(1-2/\theta+1/\theta^2)$.

isposed in the manner of an American Mathematical Monthly problem (where proposers are often already in possession of a solution); I hope this is not the case here. Meanwhile, I find this question quite intriguing. $\endgroup$ – Todd Trimble♦ Feb 16 '15 at 15:11