Generating Functions Related to Partition Formulæ for Fibonacci Numbers

Helmut Prodinger Department of Mathematics University of Stellenbosch 7602 Stellenbosch South Africa

                      hproding@sun.ac.za

Abstract The generating functions of 2 double schemes of numbers are explicitly computed using the kernel method, which leads to easy proofs of partition formulæ for Fibonacci numbers.

1 Introduction

The numbers given by the recursions

b_{n+1,k} = c_{n,k−1} + 2c_{n,k} − b_{n,k},
c_{n+1,k} = b_{n+1,k} + 2b_{n+1,k+1} − c_{n,k}

for n ≥ 0, with b_{0,0} = c_{0,0} = 1, c_{n,−1} = c_{n,0} are used by Fahr and Ringel in [1] to partition the Fibonacci numbers. We want to shed new light on these numbers, by computing their (bivariate) generating functions. These lead then also to straight forward proofs of the partition formulæ given by Fahr and Ringel in [1]. Notice, however, that these proofs do not provide any insight.

2 The generating functions

Introducing generating functions

B(z, x) := ∑_{0≤k≤n} b_{n,k}z^{n}x^{k},
C(z, x) := ∑_{0≤k≤n} c_{n,k}z^{n}x^{k},

these recursions translate into

B(z, x) = 1 + zxC(z, x) + 2zC(z, x) − zB(z, x) + zC(z, 0),
C(z, x) = B(z, x) + \frac{2}{x}[B(z, x) − B(z, 0)] − zC(z, x).

This leads to

C(z, x) = −\frac{x + z(x − 4)C(z, 0)}{zx^{2} − z^{2}x + 2zx − x + 4z} .

To solve that, we factor the denominator:

C(z, x) = \frac{−x + z(4 − x)C(z, 0)}{z(x − r_{1}(z))(x − r_{2}(z))}

with

r_{1,2}(z) = \frac{(1 − z)^{2} ± (1 + z)\sqrt{1 − 6z + z^{2}}}{2z} .

Since 1/(x − r_{2}(z)) has no power series expansion in z and x, the factor must cancel, i.e.,

−r_{2}(z) + z(4 − r_{2}(z))C(z, 0) = 0,

whence

C(z, 0) = \frac{−1 + 4z − z^{2} + (1 + z)\sqrt{1 − 6z + z^{2}}}{2z(1 − 7z + z^{2})} .

This is the famous kernel method, see, e.g., [2].

After cancellation, this leads to

C(z, x) = \frac{4r_{2}(z)}{2z(1 − 4xr_{2}(z))} \frac{1 − 10z + z^{2} + (1 + z)\sqrt{1 − 6z + z^{2}}}{1 − 7z + z^{2}} ,

and

[x^{k}]C(z, x) = \frac{(4r_{2}(z))^{k+1}}{2z} \frac{1 − 10z + z^{2} + (1 + z)\sqrt{1 − 6z + z^{2}}}{1 − 7z + z^{2}} .

From this we get

B(z, x) = \frac{−(1 + z)(z^{2}x − 8xz + 4z + x) + (−z^{2}x + 12z + 4 zx − x)\sqrt{1 − 6z + z^{2}}}{2(1 − 7z + z^{2})(−z^{2}x + 2zx − x + 4z + zx^{2})} .

The formula

f_{4(n+1)} = 3 ∑_{k≥0} 4^{k}c_{n,k},

given by Fahr and Ringel in [1], can now easily be verified, since the generating function of the right-hand side is

3C(z, 4) = \frac{3}{1 − 7z + z^{2}} ,

which is also the generating function of the left-hand side, which can be seen for example from the Binet form of the Fibonacci numbers.

The other formula

f_{4n+2} = b_{n,0} + \frac{3}{2} ∑_{k≥1} 4^{k}b_{n,k},

follows from the generating function

B(z, 0) + \frac{3}{2}(B(z, 4) − B(z, 0)) = \frac{1 + z}{1 − 7z + z^{2}} .

References

[1] Ph. Fahr and C.-M. Ringel, A partition formula for Fibonacci numbers, J. Integer Sequences 11 (2008), Article 08.1.4.

[2] H. Prodinger, The kernel method: A collection of examples, Séminaire Lotharingien de Combinatoire, B50f (2004).

2000 Mathematics Subject Classification: Primary 11B39, Secondary 16G20. Keywords: Fibonacci numbers, generating function, kernel method.

(Concerned with sequences \underline{A110122} and \underline{A132262}.)

Received February 28 2008; revised version received April 21 2008. Published in Journal of Integer Sequences, May 22 2008. Minor correction, August 12 2008.

Return to Journal of Integer Sequences home page.