# A General Formula For The X-bonacci sequences

I've been trying to work out a general formula for the X-th Fibonacci-style sequence. To be precise, a formula that outputs a set of numbers, where each number is the sum of the $x$ numbers before it. Some examples of such sets: $$\text{Fibonacci Sequence} \rightarrow \{1, 1, 2, 3, 5, 8, 13, 21, \cdots\} \\ \text{Tribonacci Sequence} \rightarrow \{1, 1, 1, 3, 5, 9, 17, 31, 57, \cdots\}\\ \text{4-bonacci Sequence} \rightarrow \{1, 1, 1, 1, 4, 7, 13, 25, \cdots\} \\\vdots$$ I have come up with three useful points.

1. The first $x$ elements of the $x$-bonacci sequence will be $1$.
2. The $x+1$-th element will be the sum of $x$ $1$s, i.e., $x$.
3. Then each element will be the sum of the $x$ elements before it. So the $x+2$-th element will be the sum of $x$ and $x-1$ $1$s $\Rightarrow$ $2x-1$.

So, the formula I came up with:

$$\varsigma(x)=\{1, 1, 1, \dots (x \text{ times}), x, 2x-1, 4x-3, 8x-7, 16x-15, 32x-31\}$$ $$\varsigma(x) = \bigcup_{i=1}^{x}{1} \cup \bigcup_{k=1}{2^k(x-1) + 1}$$

This formula works, but not always. For example, here is the comparison between the true 5-bonacci sequence and $\varsigma(5)$:

$$\text{5-bonacci Sequence} \rightarrow \\\{1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129, 253, 497, 977, 1921, 3777, 7425, 14597, 28697, 56417\}$$$$\varsigma(5) = \{1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049\}$$

The first $11$ elements are identical. Then everything just goes crazy. Extending this and observing the result, I realized that the function $\varsigma(x)$ returned the set accurate to $2x+1$ elements.

Interesting. So the $\text{151st}$ element of the $99$-bonacci sequence is $2^{151-99}\times98 + 1 \Rightarrow 49\times(2^{52}) + 1 \rightarrow 441352763482308609$.

Question:

1. Why is it that this function cannot produce a set accurate beyond the $2x+1$-th element?

• Matching up to $2x+1$ terms doesn't seem terribly interesting. You get the first $x$ terms very cheaply, and after that $a_{n+1}=2a_n-1$ from which your result follows at once. Hard to see how to generalize this further out.
– lulu
Jun 23, 2018 at 12:50
• Worth noting: the polynomial equation $x^n=x^{n-1}+\cdots +1$ doesn't have terribly nice solutions for large $n$ but it does have the property that it has one "large" root and the rest are small. For your problem, this has the implication that for large indices $i$ you can approximate your terms well by some constant times the large root to the power $i$ (as the other terms all drop off). That's pretty useful in practice.
– lulu
Jun 23, 2018 at 12:55