On a question of Cooper and Kennedy

Helmut Prodinger Department for Algebra and Discrete Mathematics TU Wien Wiedner Hauptstrasse 8–10/118 A-1040 Wien Austria email: proding@rsmb.tuwien.ac.at

In [2], Cooper and Kennedy note the following: If

x_{n} = ax_{n−1} + bx_{n−2} + cx_{n−3} ,  (1)

then

x_{n}^{2} = Ax_{n−1}^{2} + Bx_{n−2}^{2} + Cx_{n−3}^{2} + Dx_{n−4}^{2} + Ex_{n−5}^{2} + F x_{n−6}^{2} ,  (2)

where the coefficients A, B, C, D, E, F may be expressed in terms of a, b, c. They ask: Is there a similar formula for third powers? The answer is: YES. The reason is the following: Sequences which are solutions of linear recurrences with constant coefficients have ordinary generating functions which are rational. Conversely, if a rational function has no pole in z = 0, its Taylor coefficients fulfill a linear recurrences with constant coefficients. If

f := ∑_{n≥0} a_{n}z^{n} and g := ∑_{n≥0} b_{n}z^{n}  (3)

are two (formal) series, their Hadamard product is defined to be

f ⊙ g := ∑_{n≥0} a_{n}b_{n}z^{n} .  (4)

And rational functions are closed under the Hadamard product! (See [1, page 85].)

The larger (and maybe even more important) class of holonomic functions (solutions of linear differential equations with polynomial coefficients) is also closed under the Hadamard product. Their Taylor coefficients fulfill linear recursions with polynomial coefficients. There is a Maple package, Gfun, which computes (among many other useful things) the Hadamard product. (See [4].)

There is another very useful program, Ekhad, written by Doron Zeilberger ([3]), which should be mentioned. With it, we find for example recursions for the dth powers of the Fibonacci numbers F_{n} in almost no time. In the following, F_{n}^{d} will be a solution of the given recursion.

d = 1 x_{n+2} − x_{n+1} − x_{n} = 0
d = 2 x_{n+3} − 2x_{n+2} − 2x_{n+1} + x_{n} = 0
d = 3 x_{n+4} − 3x_{n+3} − 6x_{n+2} + 3x_{n+1} + x_{n} = 0
d = 4 x_{n+5} − 5x_{n+4} − 15x_{n+3} + 15x_{n+2} + 5x_{n+1} − x_{n} = 0
d = 5 x_{n+6} − 8x_{n+5} − 40x_{n+4} + 60x_{n+3} + 40x_{n+2} − 8x_{n+1} − x_{n} = 0
d = 6 x_{n+7} − 13x_{n+6} − 104x_{n+5} + 260x_{n+4} + 260x_{n+3} − 104x_{n+2} − 13x_{n+1} + x_{n} = 0

References

[1] L. Comtet. Advanced Combinatorics. Reidel, Dordrecht, 1974.

[2] C. N. Cooper and R. E. Kennedy. Proof of a result by Jarden by generalizing a proof of Carlitz. Fibonacci Quarterly, 33:304–310, 1995.

[3] M. Petkovsek, H. Wilf, and D. Zeilberger. A = B. A.K. Peters, Ltd., 1996.

[4] Bruno Salvy and Paul Zimmermann. GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable. ACM Transactions on Mathematical Software, 20(2):163–167, 1994.

1991 Mathematics Subject Classification. 11B37.