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 $

Question

Define $$A_n = \lceil e^{(n-1)/2}\rceil $$

with ceiling function $\lceil x\rceil$. Then starting with $n=0$ we get A005181,

$$A_n = 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \color{brown}{91, 149,\dots}$$

Compare to the Fibonacci numbers,

$$F_n = 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \color{brown}{89, 144,\dots}$$

---

I was wondering if this had a tribonacci counterpart. After some quick experimentation, if we define $$B_n = \lceil e^{\pi(n-1)/5}\rceil $$

then,

$$B_n = 1, 1, 2, 4, 7, 13, 24, 44, \color{brown}{82, 153,\dots}$$

Compare to the tribonacci numbers,

$$T_n = 1, 1, 2, 4, 7, 13, 24, 44, \color{brown}{81, 149,\dots}$$

Questions:

1. What is the tetranacci counterpart?
2. Is there a reason why such a family would exist other than mere coincidence?

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