A combinatorial proof for the generating function of powers of a second-order recurrence sequence.(English)Zbl 1384.05033
Summary: In this paper, we derive a formula for the generating function of powers of a second-order linear recurrence sequence, with initial conditions 0 and 1. As an example, we find the generating function of the powers of the nonnegative integers. We also find new formulas for computing Eulerian polynomials.
MSC:
| 05A15 | Exact enumeration problems, generating functions |
| 05A10 | Factorials, binomial coefficients, combinatorial functions |
| 11B68 | Bernoulli and Euler numbers and polynomials |
Keywords:
generating function;second-order recurrence sequence;Pascal triangle;matrix;Eulerian polynomialSoftware:
OEISCite
Online Encyclopedia of Integer Sequences:
Product of Fibonacci and Pell numbers.Triangle of Eulerian numbers T(n,k) (n >= 1, 1 <= k <= n) read by rows.
a(n) = 3*a(n-1) + a(n-2) - a(n-3) for n >= 3, a(0)=1, a(1)=2, a(2)=7.
References:
| [1] | L. E. Dickson, {\it History of the Theory of Numbers}, Carnegie Institution, 1919. ·JFM 47.0100.04 |
| [2] | A. Dujella, A bijective proof of Riordan’s theorem on powers of Fibonacci numbers, {\it Discrete Math. }199(1999), 217-220. 14 ·Zbl 0936.11010 |
| [3] | M. Katz and C. Stenson, Tiling a (2 × n)-board with squares and dominoes, {\it J. Integer} {\it Sequences }12(2009),Article 09.2.2. ·Zbl 1228.05062 |
| [4] | T. Mansour, A formula for the generating functions of powers of Horadam’s sequence, {\it Australas. J. Combin. }30(2004), 207-212. ·Zbl 1053.05008 |
| [5] | J. Riordan, Generating functions for powers of Fibonacci numbers, {\it Duke Math. J. }29 (1962), 5-12. ·Zbl 0101.28801 |
| [6] | J. A. Sellers, Domino tilings and products of Fibonacci and Pell Numbers, {\it J. Integer} {\it Sequences }5(2002),Article 02.1.2. ·Zbl 1125.11011 |
| [7] | N. J. A. Sloane, {\it The On-line Encyclopedia of Integer Sequences}, http://www.oeis.org. ·Zbl 1274.11001 |
| [8] | P. St˘anic˘a, Generating functions, weighted and non-weighted sums for powers of second order recurrence sequences, {\it Fibonacci Quart. }41 (2003), 321-333. ·Zbl 1130.11307 |
| [9] | Y. Zhang and G. Grossman, A combinatorial proof for the generating function of powers of the Fibonacci sequence, {\it Fibonacci Quart. }55 (2017), 235-242. ·Zbl 1401.11051 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
