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.  
 A: I would say that an asymptotic expansion formula for H(n) would suffice. That is, one has
$$
H(n)=\log n + \gamma + \frac{1}{2n}+... .,
$$
and the error terms are quite controllable.
Assuming all i,j,k of the same order of magnitude, you can rewrite the condition $H(k)>2H(j)-H(i)$ as $H(k)-H(j)>H(j)-H(i)$ and thus as
$$
\log \frac{k}{j} + (\frac{1}{2k}-\frac{1}{2j})+ \dots > \log \frac{j}{i} + (\frac{1}{2j}-\frac{1}{2i})+ \dots
$$
If there would be only the first terms, and no integer restriction, the equality in the above formula would correspond to the geometric sequence: $k/j=j/i$.
Now, roughly speaking, you get the Fibonacci sequence, because it is so close to the geometric one (error at $F_n$ is of magnitude $\sim 1/F_n$). Well, you will need some fine analysis to check that for $i=F_{n-1}$ and $j=F_n$ the inequality holds at $k=F_{n+1}$ and does not at $k=F_{n+1}-1$, but the difference between the left hand sides are "quite large" (that is, $1/k$), and you control the error terms as precise as you'd like to (see formula (13) here -- http://mathworld.wolfram.com/HarmonicNumber.html ). The rest should be pure (and not so difficult) technique: just check the $\sim 1/k$ terms for $k=F_{n+1}$ and for $k=F_{n+1}-1$, check that they are of opposite signs, and control the error terms.
A: 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)$.
