# 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.

• This is worded like homework.. can you give maybe more background on this problem? – Per Alexandersson Feb 16 '15 at 15:03
• I am pretty sure it's not homework, since the author is by all appearances a well-established mathematician. But it is posed 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. – Todd Trimble Feb 16 '15 at 15:11
• Some background: this problem results from Mathematica-based explorations of the harmonic numbers $H(n).$ Many choices of $i$ and $j$ lead to sequences $(a_n)$ that appear to be linearly recurrent. Among them, the case $(i,j)$ = $(5,8)$ is my favorite. The recent MathOverflow problem "A possibly surprising appearance of Lucas numbers" also yields sequences that may be linearly recurrent, but for which proofs (or counterexamples) appear to be nontrivial. As far as I know, both of these possibly surprising appearances are new. – Clark Kimberling Feb 16 '15 at 16:12

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

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.