6
$\begingroup$

My question is simple, but a mystery to me. Skip to the last paragraph if you're not interested in the story of my exploration.

EDIT: I seem to have misinterpreted a key detail regarding how the sequence relates to the continued fraction expansion of $\sqrt{5}$ which I've fixed in this post. See the comments for more info.

The background: I had the brilliant idea to consider the Fibonacci-like sequence which starts with $$\frac{1 \pm \sqrt{5}}{2}$$ as initial values, and see what happens. Nothing too interesting, it just devolves into $$T_n = \frac{F_n + F_{n-2}\sqrt{5}}{2}$$ fairly quickly ($\forall n \geq 4$); this has nothing to do with the presence of $\sqrt{5}$ as opposed to any other value, though.

However, the 2 in the denominator gave me something to work with: every third Fibonacci number is certainly even, which means I can reduce every third element of this sequence I've constructed. The first couple of these, reduced, are: $$\begin{array}{c|ccccc}n & 3 & 6 & 9 & 12 & 15\\ \hline T_n & 0\sqrt{5}+1 & 1\sqrt{5}+4 & 4\sqrt{5}+17 & 17\sqrt{5}+72 & 72\sqrt{5}+305 & \end{array}$$

It was at this point that I realized all I was doing was taking the $3n$th Fibonacci number and dividing it by two, which was kind of boring. I figured I'd look up the sequence on the OEIS, though, and it seems to be the sequence of denominators you get after truncating the continued fraction expansion of $\sqrt{5}$ after some number of denominators and then simplifying.

The question: why?

$\endgroup$
10
  • $\begingroup$ I think I misunderstand you: per this question, the continued fraction expansion of $\sqrt{5}$ is a bunch of $4$'s. $\endgroup$ – Eli Rose Jun 5 '15 at 1:27
  • $\begingroup$ Can you add a link to the OEIS sequence you allude to? $\endgroup$ – Semiclassical Jun 5 '15 at 1:30
  • $\begingroup$ @EliRose I think I misunderstood what the OEIS was saying! oeis.org/A001076 this is a link to the sequence. I have no idea what a "continued fraction convergent" is if it's not the thing I thought. My fault though, I should have checked more carefully before posting. Edit: It's probably the bottom denominator of the $n$-term-deep approximation. $\endgroup$ – Samuel Yusim Jun 5 '15 at 1:32
  • $\begingroup$ I've fixed the post. $\endgroup$ – Samuel Yusim Jun 5 '15 at 1:42
  • 1
    $\begingroup$ Generally, it is wise to get to your question first then give any backstory. It makes it easier for people who, after all, are volunteers, to quickly determine if they can help you. And years from now, if somebody googles and encounters your question, will it be obvious to them quickly if it is the same as their own? And, as a rule, the question should never be "long paragraph" then "why?" Make the question clear to someone scanning, as much as possible $\endgroup$ – Thomas Andrews Jun 5 '15 at 1:52
7
$\begingroup$

Recursion for the $3n\,$th Fibonacci number: let $G_n=F_{3n}$. Then we have $$\eqalign{ G_{n+1}&=F_{3n+2}+F_{3n+1}\cr F_{3n+2}&=F_{3n+1}+G_n\cr 2F_{3n+1}&=2G_n+2F_{3n-1}\cr -G_n&=-F_{3n-1}-F_{3n-2}\cr F_{3n-1}&=F_{3n-2}+G_{n-1}\ .\cr}$$ Now add all these equations: lots of things cancel and we get $$G_{n+1}=4G_n+G_{n-1}\ .$$ For the convergents $p_n/q_n$ of a continued fraction we have $$q_{n+1}=a_nq_n+q_{n-1}\ .$$ In the case of $\sqrt5$ all of the $a_n$ for $n\ge1$ are equal to $4$, so we have $$q_{n+1}=4q_n+q_{n-1}\ .$$ This is the same as the recurrence for $G_n$, so as long as the initial values match, the sequences will be identical.

$\endgroup$
1
  • 1
    $\begingroup$ The central identity here (the recursion for $F_{3n}$ appears as the $k=3$ case of equation (44) of Mathworld's page on Fibonnaci numbers: $$F_{nk}=L_k F_{n(k-1)}-(-1)^k F_{n(k-2)}$$ where $L_k$ is the $k$th Lucas number. So the result for continued-fraction convergents obtained above can be generalized to generic $k$. $\endgroup$ – Semiclassical Jun 5 '15 at 3:19

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.