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.
- The first $x$ elements of the $x$-bonacci sequence will be $1$.
- The $x+1$-th element will be the sum of $x$ $1$s, i.e., $x$.
- 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?
