On the pseudo-Fibonacci and pseudo-Tribonacci sequences $A_n = \lceil e^{(n-1)/2}\rceil $ and $B_n = \lceil e^{\pi(n-1)/5}\rceil $

Solution 1:

One should expect that there should be some approximations like this. It's not clear that there's an instructive analytic way to produce the best such approximation (one can in any case improve on $\frac{\pi}{5}$ for the Tribonacci sequence, see below), but probably there are ways to generate reasonably good choices that are canonical in some sense.

Fibonacci The Fibonacci sequence can be written using the given indexing as (this is Binet's Formula) $$F_n = \frac{1}{\sqrt{5}} \phi^{n + 1} - \frac{1}{\sqrt{5}}\left(-\frac{1}{\phi}\right)^{n + 1} ,$$ where $\phi := \frac{1 + \sqrt{5}}{2} = 1.61803\!\ldots$ is the Golden Ratio. Now, the second term is small and decreases rapidly with $n$, so $F_n \approx \frac{1}{\sqrt{5}} \phi^{n + 1}$, which can in turn be written in the form $e^{\alpha + \beta n}$, where $$\alpha = -\frac{1}{2} \log 5 + \log \phi = -0.32350\!\ldots, \qquad \beta = \log \phi = 0.48122\!\ldots .$$ Thus, by adjusting $\alpha$ and/or $\beta$, so that for small $n$ the total quantity is smaller than that the original exponential expression by at least the absolute value of the discarded term, at least for small $n$, we might expect to be able to produce $\alpha, \beta$ such that $$\lceil e^{\alpha + \beta n} \rceil = F_n \qquad \textrm{for small $n$}.$$ So, the fact that $F_n \approx \lceil e^{(n - 1) / 2} \rceil$ is partly a consequence of the approximation $\phi^2 \approx e$. N.b. the (linear) inequalities $$F_n - 1 < e^{\alpha + \beta n} \leq F_n, \qquad n = 0,\ldots,10,$$ cannot be satisfied simultaneously, so no choice of $\alpha, \beta$ yields more matching terms at the beginning of the sequence than the given choice $\alpha = -\frac{1}{2}, \beta = \frac{1}{2}$.

Something similar happens for the next few generalized Fibonnaci sequences.

Tribonacci The analogue of Binet's Formula is $$T_n = \zeta r^n + \eta s^n + \bar\eta \bar s^n$$ for some constants $\zeta, \eta$ where $r = 1.83929\!\ldots, s, \bar s$ are the three roots of the characteristic polynomial $x^3 - x^2 - x - 1 = 0$ of the Tribonacci recursion $T_{n + 3} = T_{n + 2} + T_{n + 1} + T_n$. Now, $|\Re s| = \frac{1}{2} (r - 1) < 1$, so $T_n \approx \zeta r^n = \exp(\alpha + n \beta)$, where $$\alpha = \log \zeta, \qquad \beta = \log r = 0.60937\!\ldots ,$$ and $\frac{\pi}{5} = 0.62831\!\ldots$ is certainly close to the latter. One can do a little better by taking $-\alpha = \beta$ to be $\frac{32}{51} = 0.62745\!\ldots$ or $\frac{4}{7} \log 3 = 0.62777\!\ldots$ (so that $e^{\beta} = 3^{4/7} = 1.87344\!\ldots$), both of which recover $T_8 = 81$, but one cannot reproduce any more terms.

Tetranacci The Tetranacci sequence is asymptotic to $\zeta r^n$ where $r = 1.92756\!\ldots$ is the largest real root of the characteristic polynomial $x^4 - x^3 - x^2 - x - 1$, so we expect $\beta \approx \log r = 0.65625\!\ldots$. This time the best we can do, at least when $\alpha = -\beta$, is reproducing all of the terms up through $108$, and taking $\beta = \frac{2}{3}$ will do so.