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 possibly surprising appearance of Fibonacci numbers
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](http://en.wikipedia.org/wiki/Pisot%E2%80%93Vijayaraghavan_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)$.


