A possibly surprising appearance of Fibonacci numbers Let $H(n) = 1/1 + 1/2 + \dotsb + 1/n,$ and for $i \leq j,$ let $a_1$ be the least $k$ such that 
$$H(k) > 2H(j) - H(i),$$
let $a_2$ be the least k such that
$$H(k) > 2H(a_1) - H(j),$$
and for $n \geq 3,$ let $a_n$ be the least $k$ such that
$$H(k) > 2H(a_{n-1}) - H(a_{n-2}).$$
Prove (or disprove) that if $i = 5$ and $j = 8$, then $(a_n)$ is the sequence $(5,8,13,21,\dotsc)$ of Fibonacci numbers, and determine all $(i,j)$ for which $(a_n)$ is linearly recurrent.  

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)$.
