23
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This is worded like homework.. can you give maybe more background on this problem? $\endgroup$ – Per Alexandersson Feb 16 '15 at 15:03
  • 3
    $\begingroup$ 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. $\endgroup$ – Todd Trimble Feb 16 '15 at 15:11
  • 6
    $\begingroup$ 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. $\endgroup$ – Clark Kimberling Feb 16 '15 at 16:12
  • 1
    $\begingroup$ @ClarkKimberling I've noticed that you've asked a lot of questions (24), but never accepted any answers. On the questions that you ask, for answer there is a small check mark underneath the up and down arrows for that answer. If someone answered one of your questions satisfactorily, you can click on the small check mark underneath the downarrow for that answer, and it will turn green. This marks the chosen answer as "accepted" and marks the question as having an accepted answer. It also rewards the user who answered your question. $\endgroup$ – Eric Naslund Jan 19 '16 at 22:00
29
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.