Solutions for k -Generalized Fibonacci Numbers Using Fuss-Catalan Numbers

We present new expressions for the k-generalized Fibonacci numbers, say Fk(n). They satisfy the recurrence Fk(n)=Fk(n−1)+…+Fk(n−k). Explicit expressions for the roots of the auxiliary (or characteristic) polynomial are presented, using Fuss-Catalan numbers. Properties of the roots are enumerated. We quantify the accuracy of asymptotic approximations for Fk(n) for n≫1. Our results subsume and extend some results published by previous authors. We also present a basis (or “fundamental solutions”) to solve the above recurrence for arbitrary initial conditions. We comment on the use of generating functions and multinomial sums for the k- generalized Fibonacci numbers and related sequences. We note that the resulting multinomial sums are Dickson polynomials of the second kind in several variables. We also present what may be a new identity for companion matrices.