2
$\begingroup$

Consider a generalized Fibonacci sequence $f_n=af_{n-1}+bf_{n-2}$ with initial conditions $f_0 ~\& ~f_1$. We have shown a general solution here that can be expressed in a myriad of ways, including

$$ f_n=f_1F_n+bf_0F_{n-1}\\ F_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}\\ \alpha,\beta=\frac{a\pm\sqrt{a^2+4b}}{2} $$

This equation is valid for any real or complex values of $f_0,~f_1,~a,~\&~b$. Integer sequences accrue only when all of them are integers, however.

Now, when the radical in $\alpha,\beta$ is real, so are $\alpha,\beta$ and the limit of consecutive quotients is given by

$$\lim_{n\to\infty}\frac{f_{n+1}}{f_n}=\alpha$$

However, when that radical is imaginary, then $\alpha,\beta$ are complex conjugates and both $F_n$ and $\frac{f_{n+1}}{f_n}$ are oscillatory. Nevertheless, the sequences are real. (Many such sequences can be found in the OEIS.) To see how this arises, consider

$$ \begin{align} F_n &=\frac{\alpha^n-\beta^n}{\alpha-\beta} =\frac{\alpha^n-(\alpha^*)^n}{\alpha-\alpha^*}\\ &=\frac{\mathfrak{Im}\{\alpha^n\}}{\mathfrak{Im}\{\alpha\}} =|\alpha|^{n-1}\frac{\sin n\theta}{\sin \theta} \end{align} $$

Similarly, for the simplified case when $f_0=0$, the limit of consecutive quotients is given by $$ \begin{align} \lim_{n\to\infty}\frac{f_{n+1}}{f_n} &=\lim_{n\to\infty}\frac{F_{n+1}}{F_n}\\ &=\frac{\mathfrak{Im}\{\alpha^{n+1}\}}{\mathfrak{Im}\{\alpha^n\}} =|\alpha|\frac{\sin (n+1)\theta}{\sin n\theta}\\ \end{align} $$

The figure below shows a typical limit ratio versus $n$. The behavior is seen to be oscillatory, but not periodic. It almost looks chaotic, what with quasi-repeating patterns and several obvious frequencies.

I'm seek help to characterize this behavior. I have tried treating it as a 'signal' but did not get very far with either the FFT or HHT (Hilbert-Huang transform), though I readily admit to having not used either in several years.

example complex base limit quotient

$\endgroup$
  • $\begingroup$ What is the question? You already have a very clean closed formula: what else do you want to know? $\endgroup$ – Qiaochu Yuan Sep 4 '17 at 21:17
  • $\begingroup$ @QiaochuYuan I want to be able characterize the figure in the sense of determining the characteristic frequencies, or spacing between the peaks, and how they relate to the input parameters. As I said, treat it like a signal. What can you tell me about it. Having the equation allows me to plot it, but doesn't tell me anything else about it. $\endgroup$ – Cye Waldman Sep 4 '17 at 22:58
  • $\begingroup$ The closed formula tells you all sorts of things about it. For starters, note that if $\theta$ is a rational multiple of $\pi$ then the closed formula implies that the sequence is periodic. If $\theta$ is close to some rational multiple of $\pi$ then it is close to periodic, as you've observed, so the question of what the periodicities look like is straightforwardly tied to the question of how to approximate $\frac{\theta}{\pi}$ by rationals. $\endgroup$ – Qiaochu Yuan Sep 5 '17 at 4:04

Your Answer

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

Browse other questions tagged or ask your own question.