Tribonacci to Infinity

Let's generalize this. For positive integer $n\geq 2$ , denote $n$ -bonacci numbers to be the sequence of numbers that follows the recurrence relation that each term is the sum of the previous $n$ terms, with initial conditions of $a_{0,n} = a_{1,n} = \ldots = a_{n-1,n} = 0, a_{n,n} = 1$ .

Comparing it to Newton's Identity and letting $\large \displaystyle G_{n} = \lim_{m \to \infty} \frac {a_{m,n}}{a_{m-1,n}}$ , we have $G_n$ satisfying the equation below

$x^{n} - x^{n-1} - x^{n-2} - \ldots - x - 1 = 0$

In this case, $n=3$ , which we get $Q = G_3$ thus

$Q^3 - Q^2 - Q - 1 = 0 \Rightarrow Q^3 - Q^2 - Q = \boxed{1}$

Python 2.7:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

memo = {0:0.0, 1:1.0, 2:1.0}
def trib(n):
    if n in memo:
        return memo[n]
    memo[n] = trib(n-1)+trib(n-2)+trib(n-3)
    return memo[n]
# build table to reduce recursion
infinity = 1000
for i in xrange(infinity):
    trib(i)
Q = trib(infinity)/trib(infinity-1)
print "Answer:", Q**3-Q**2-Q