# Finding the kth n-anacci number

At this wolfram link the formula for the kth n-anacci number is given:

http://mathworld.wolfram.com/Fibonaccin-StepNumber.html#eqn8

(Eq. 4)

Not sure if I understand correctly. If I want the fifth tribonacci (n=3) number does the following do the trick?

$$F_5^{(3)}=\sum_{i=1}^{3}\frac{x^5_i}{-x_i^2+4x_i-1}$$

But then what are the $x_i$? I understand that they are the roots of the polynomial $x^n(2-x)=1$ (Eq. 2 at the link) but the only really important root here is the n-anacci constant (which for eg. is $\phi$, the golden ratio, when n=2). I'm not even sure how to get my software to spit out the other roots.

-
I believe most software can spit out all the three roots. You might need to tell it specifically though. – Tunococ Sep 7 '12 at 5:22
Does Section 5 at the following web site help? haskell.org/haskellwiki/The_Fibonacci_sequence – Amzoti Sep 7 '12 at 5:55
$x^n(2-x)-1 = (x-1)(1+x+\cdots+x^{n-1}-x^n)$. Thus for $n=3$ you have to find the roots of $1+x+x^2-x^3$ (one is real, two complex). For degree 3 and 4 there are still "exact" methods (i.e using radicals) available, but I'd usually settle with a good numerical approximation. – Hagen von Eitzen Sep 7 '12 at 5:58