A note on Fibonacci-type polynomials

We opt to study the convergence of maximal real roots of certain Fibonacci-type polynomials given by Gn = xGn−1 + Gn−2. The special cases k = 1 and k = 2 are found in [4] and [7], respectively. In the sequel, P denotes the set of positive integers. The Fibonacci polynomials [2] are defined recursively by F0(x) = 1, F1(x) = x and Fn(x) = xFn−1(x) + Fn−2(x), n ≥ 2. Fact 1. Let n ≥ 1. Then the roots of Fn(x) are given by xk = 2i cos ( πk n+ 1 ) , 1 ≤ k ≤ n. In particular a Fibonacci polynomial has no positive real roots. Proof. The Fibonacci polynomials are essentially Tchebycheff polynomials. This is well-known (see, for instance [2]). Let k ∈ P be fixed. Several authors ([3]-[7]) have investigated the so-called Fibonacci-type polynomials. In this note, we focus on a particular group of polynomials recursively defined by G n (x) =  −1, n = 0 x− 1, n = 1 xG (k) n−1(x) +G (k) n−2(x), n ≥ 2. When there is no confusion, we suppress the index k to write Gn for G (k) n (x). We list a few basic properties relevant to our work here. Fact 2. For each k ∈ P, there is a rational generating function for Gn; namely, ∑ n≥0 G n (x)t n = (x + x− 1)t− 1 1− xkt− t2 . Proof. The claim follows from the definition of Gn. Typeset by AMS-TEX 1 2 TEWODROS AMDEBERHAN Fact 3. The following relation holds G n (x) = G (k) n−1Fn−1(x ) + (−1)n−1 Fn−2(x) . Proof. We write the equivalent formulation G n (x) = det  x− 1 −1 0 0 . . . 0 0 0 −1 x −1 0 . . . 0 0 0 0 1 x −1 . . . 0 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 0 . . . x −1 0 0 0 0 0 . . . 1 x −1 0 0 0 0 . . . 0 1 x  , then we apply Dodgson′s determinantal formula [1]. Fact 4. For a fixed k, let {g n }n∈P be the maximal real roots of {G n (x)}n. Then {g 2n }n and {g 2n−1}n are decreasing and increasing sequences, respectively. Proof. First, each gn exists since Gn(0) = 1 0. Invoking Fact 3 from above, twice, we find that F2n−3(x)G (k) 2n (x) = F2n−1(x k)G 2n−2(x) + x , F2n−2(x)G (k) 2n+1(x) = F2n(x k)G 2n−1(x)− x. From these equations and Fn(x) > 0 (see Fact 1), it is clear that G2n−2(x) > 0 implies G2n(x) > 0; also if G2n−2(x) = 0 then G2n(x) > 0. Thus g2n−2 > g2n. A similar argument shows g2n+1 > g2n−1. The proof is complete. Define the quantities α(x) = x+ √ x2 + 4 2 , β(x) = x− √ x2 + 4 2 , p(x) = (x− 1) + β(x) α(xk)− β(xk) , q(x) = (x− 1) + α(x) α(xk)− β(xk) . Fact 5. For n ≥ 0 and k ∈ P, we have the explicit formula G n (x) = p(x)α (x)− q(x)β(x). Proof. This is the standard generalized Binet formula. A NOTE ON FIBONACCI-TYPE POLYNOMIALS 3 For each k ∈ P, we introduce another set of polynomials H(x) = x − xk−1 + x− 2. Fact 6. For each k ∈ P, the polynomial H(x) has exactly one positive real root ξ > 1. Proof. Since H(x) = (x − 1)(xk−1 + 1) − 1 0 whenever x ∈ P, suggest there is only one positive root (necessarily greater than 1). Fact 7. If k is odd (even), then H(x) has no (exactly one) negative real root. Proof. For k odd, H(−x) = (−x−1)(xk−1+1)−1 < 0. For k even, H(−x) = xk+xk−1−x−2 changes sign only once. We now apply Descartes′ Rule to infer the claim. Now, we state and prove the main result of the present note. Theorem. Preserve the notations of Facts 4 and 6. Then, depending on the parity of n, the roots {g n }n converge from above or below so that g n → ξ as n→∞. Note also ξ → 1 as k →∞. Proof. For notational brevity, we suppress k and write gn and ξ. From Gn(gn) = 0 and Fact 5 above, we resolve (1) p(gn) q(gn) = β(g n) αn(gk n) , or 2(gn − 1) + g n − √ g2k n + 4 2(gn − 1) + gk n + √ g2k n + 4 = (−1) ( 1− 2gn gk n + √ g2k n + 4 )n . Using Gershgorin′s Circle theorem, it is easy to see that 1 ≤ gn ≤ 2. When combined with Fact 4, the monotonic sequences {g2n}n and {g2n−1}n converge to finite limits, say ξ+ and ξ− respectively. The right-hand side of (1) vanishes in the limit n→∞, thus 2(ξ − 1) + ξ − √ ξ2k + 4 = 0. Further simplification leads to H(ξ) = ξ − ξk−1 + ξ − 2 = 0. From Fact 6, such a solution is unique. So, ξ+ = ξ− = ξ completes the proof. Further Comments In this section, we discuss the bivariate Fibonacci polynomials, of the first kind (BFP1), defined as gn(x, y) = xgn−1(x, y) + ygn−2(x, y), g0(x, y) = x, g1(x, y) = y. If x = y = 1 then the resulting sequence is the Fibonacci numbers. The following is a generating function for the BFP1 ∑ n≥0 gn(x, y)t = x+ (y − x)t 1− xt− yt2 . 4 TEWODROS AMDEBERHAN It is also possible to give an explicit expression gn(x, y) = ∑ k≥1 2n− 3k + 1 n− k ( n− k k − 1 ) xn−2k+1yk. This shows clearly that each BFP1 has nonnegative coefficients. The other variant that appears often in the literature is what we call bivariate Fibonacci polynomials, of the second kind (BFP2). These are recursively defined as fn(x, y) = xfn−1(x, y) + yfn−2(x, y), f0(x, y) = y, f1(x, y) = x. Obviously fn(1, 1) yields the Fibonacci numbers. We also find the ordinary generating function ∑ n≥0 fn(x, y)t = y + (x− xy)t 1− xt− yt2 . One interesting contrast between the two families is the following. While the roots of fn(x, 1) are all imaginary, the roots of gn(1, y) are all real numbers. Using the corresponding generating functions for BFP2 fn(x, y) and the classical Fibonacci polynomials Fn(x) = fn(x, 1) proves the below affine relation fn(x, y) = xyFn−1(x/y) + yFn−2(x/y). In particular, the Jacobsthal-Lucas numbers Jn = fn(2, 1) can be expreesed in terms of values of the Fibonacci polynomials, at 1/ √ 2, namely that Jn = 2 n−1 2 Fn−1 ( 1 √ 2 ) + 2 n 2 Fn−2 ( 1 √ 2 ) . This translates to the identity bn/2c ∑ k=0 5n− 9k n− k ( n− k k ) 2 = 2 + (−1), for n ∈ P.