On Recurrences of Fahr and Ringel Arising in Graph Theory

Michael D. Hirschhorn School of Mathematics and Statistics UNSW Sydney NSW 2052 Australia

        m.hirschhorn@unsw.edu.au

Abstract

We solve certain recurrences given by Fahr and Ringel, and confirm their conjecture that two sequences are identical.

1 Introduction

Fahr and Ringel introduce two tables of numbers, the b_{t}[r] and c_{t}[r], given by

b_{t}[r]  c_{t}[r]
r  r
0 1 2 3 4 ⋯  0 1 2 3 4 ⋯
t 0 1  t 0 1
1 2 1  1 3 1
2 7 4 1  2 12 5 1
3 29 18 6 1  3 53 25 7 1
4 130 85 33 8 1  4 247 126 42 9 1

and the recurrences

b_{t+1}[r] = c_{t}[r − 1] + 2c_{t}[r] − b_{t}[r],
c_{t+1}[r] = b_{t+1}[r] + 2b_{t+1}[r + 1] − c_{t}[r],

which hold for t, r ≥ 0, with the understanding that c_{t}[−1] = c_{t}[0].

The object of this note is to determine the generating functions of the b_{t}[r] and c_{t}[r], and to prove that

F_{4t+2} = b_{t}[0] + 3 ∑_{r≥1} 2^{2r−1}b_{t}[r], F_{4t+4} = 3 ∑_{r≥0} 2^{2r}c_{t}[r],

where the F_{t} are the Fibonacci numbers, given by F_{0} = 0, F_{1} = 1 and F_{t} = F_{t−1} + F_{t−2} for t ≥ 2.

2 The solution

Let us define

B_{r} = B_{r}(q) = ∑_{t≥0} b_{t}[r]q^{t}, C_{r} = C_{r}(q) = ∑_{t≥0} c_{t}[r]q^{t}.

The first few B_{r}, C_{r} are

B_{0} = 1 + 2q + 7q^{2} + 29q^{3} + 130q^{4} + ⋯,
B_{1} = q + 4q^{2} + 18q^{3} + 85q^{4} + ⋯,
B_{2} = q^{2} + 6q^{3} + 33q^{4} + ⋯,
C_{0} = 1 + 3q + 12q^{2} + 53q^{3} + 247q^{4} + ⋯
C_{1} = q + 5q^{2} + 25q^{3} + 126q^{4} + ⋯,
C_{2} = q^{2} + 7q^{3} + 42q^{4} + · · · .

Note that for r ≥ 0,

B_{r} ≡ 0 (mod q^{r}), C_{r} ≡ 0 (mod q^{r}).

From the recurrences given above, we have

B_{0} = 1 + 3qC_{0} − qB_{0},

or,

B_{0} = \frac{1 + 3qC_{0}}{1 + q} .

Also, for r ≥ 1,

B_{r} = qC_{r−1} + 2qC_{r} − qB_{r}

and for r ≥ 0,

C_{r} = B_{r} + 2B_{r+1} − qC_{r}.

That is, for r ≥ 0,

B_{r+1} = \frac{1}{2} ((1 + q)C_{r} − B_{r})

and

C_{r+1} = \frac{1}{2q} ((1 + q)B_{r+1} − qC_{r}) .

It follows that

B_{1} = \frac{1}{2} ((1 + q)C_{0} − \frac{1 + 3qC_{0}}{1 + q} ) = \frac{(1 − q + q^{2})C_{0} − 1}{2(1 + q)},

C_{1} = \frac{1}{2q} ((1 + q)\frac{(1 − q + q^{2})C_{0} − 1}{2(1 + q)} − qC_{0}) = \frac{(1 − 3q + q^{2})C_{0} − 1}{4q},

B_{2} = \frac{(1 − 3q − 2q^{2} − 3q^{3} + q^{4})C_{o} − (1 + q^{2})}{8q(1 + q)},

C_{2} = \frac{(1 − 5q + 4q^{2} − 5q^{3} + q^{4})C_{0} − (1 − 2q + q^{2})}{16q^{2}},

B_{3} = \frac{(1 − 5q + q^{2} + 2q^{3} + q^{4} − 5q^{5} + q^{6})C_{0} − (1 − 2q − 2q^{2} − 2q^{3} + q^{4})}{32q^{2}(1 + q)},

C_{3} = \frac{(1 − 7q + 11q^{2} − 6q^{3} + 11q^{4} − 7q^{5} + q^{6})C_{0} − (1 − 4q + 2q^{2} − 4q^{3} + q^{4})}{64q^{3}},

and so on.

It is clear that we can write

B_{r} = \frac{P_{r}C_{0} − Q_{r}}{2^{2r−1}q^{r−1}(1 + q)},

C_{r} = \frac{S_{r}C_{0} − T_{r}}{2^{2r}q^{r}} ,

where P_{r}, Q_{r}, S_{r}, T_{r} are polynomials in q. The first few are

P_{1} = 1 − q + q^{2}, P_{2} = 1 − 3q − 2q^{2} − 3q^{3} + q^{4}, P_{3} = 1 − 5q + q^{2} + 2q^{3} + q^{4} − 5q^{5} + q^{6}, Q_{1} = 1, Q_{2} = 1 + q^{2}, Q_{3} = 1 − 2q − 2q^{2} − 2q^{3} + q^{4}, S_{1} = 1 − 3q + q^{2}, S_{2} = 1 − 5q + 4q^{2} − 5q^{3} + q^{4}, S_{3} = 1 − 7q + 11q^{2} − 6q^{3} + 11q^{4} − 7q^{5} + q^{6}, T_{1} = 1, T_{2} = 1 − 2q + q^{2}, T_{3} = 1 − 4q + 2q^{2} − 4q^{3} + q^{4}.

It follows from the recurrences for the B_{r} and C_{r} that P_{r}, Q_{r}, S_{r} and T_{r} all satisfy the recurrence

X_{r+2} − (1 − q)^{2}X_{r+1} + 4q^{2}X_{r} = 0.

Indeed, in terms of α and β, the roots of z^{2} − (1 − q)^{2}z + 4q^{2} = 0,

α = \frac{(1 − q)^{2} + (1 + q)\sqrt{1 − 6q + q^{2}}}{2} = 1 − 2q − 3q^{2} − 8q^{3} − 28q^{4} − 112q^{5} − ⋯,

β = \frac{(1 − q)^{2} − (1 + q)\sqrt{1 − 6q + q^{2}}}{2} = 4q^{2} + 8q^{3} + 28q^{4} + 112q^{5} + ⋯,

we have

P_{r} = (\frac{3}{4} + \frac{1 + q}{4\sqrt{1 − 6q + q^{2}}} ) α^{r} + (\frac{3}{4} − \frac{1 + q}{4\sqrt{1 − 6q + q^{2}}} ) β^{r},

Q_{r} = (\frac{1 + q}{4q\sqrt{1 − 6q + q^{2}}} − \frac{1}{4q} ) α^{r} − (\frac{1 + q}{4q\sqrt{1 − 6q + q^{2}}} + \frac{1}{4q} ) β^{r},

S_{r} = (\frac{1}{2} + \frac{1 − 4q + q^{2}}{2(1 + q)\sqrt{1 − 6q + q^{2}}} ) α^{r} + (\frac{1}{2} − \frac{1 − 4q + q^{2}}{2(1 + q)\sqrt{1 − 6q + q^{2}}} ) β^{r},

T_{r} = \frac{1}{(1 + q)\sqrt{1 − 6q + q^{2}}} α^{r} − \frac{1}{(1 + q)\sqrt{1 − 6q + q^{2}}} β^{r}.

It follows that

2^{2r−1}q^{r−1}(1 + q)B_{r} = P_{r}C_{0} − Q_{r}

= ((\frac{3}{4} + \frac{1 + q}{4\sqrt{1 − 6q + q^{2}}} ) C_{0} − (\frac{1 + q}{4q\sqrt{1 − 6q + q^{2}}} − \frac{1}{4q} )) α^{r}

+ ((\frac{3}{4} − \frac{1 + q}{4\sqrt{1 − 6q + q^{2}}} ) C_{0} + (\frac{1 + q}{4q\sqrt{1 − 6q + q^{2}}} + \frac{1}{4q} )) β^{r}

and

2^{2r}q^{r}C_{r} = ((\frac{1}{2} + \frac{1 − 4q + q^{2}}{2(1 + q)\sqrt{1 − 6q + q^{2}}} ) C_{0} − \frac{1}{(1 + q)\sqrt{1 − 6q + q^{2}}} ) α^{r}

+ ((\frac{1}{2} − \frac{1 − 4q + q^{2}}{2(1 + q)\sqrt{1 − 6q + q^{2}}} ) C_{0} + \frac{1}{(1 + q)\sqrt{1 − 6q + q^{2}}} ) β^{r}.

Since the left–hand–sides of the above two equations are congruent to 0 modulo q^{2r−1}, we deduce that

(\frac{3}{4} + \frac{1 + q}{4\sqrt{1 − 6q + q^{2}}} ) C_{0} − (\frac{1 + q}{4q\sqrt{1 − 6q + q^{2}}} − \frac{1}{4q} ) = 0,

alternatively that

(\frac{1}{2} + \frac{1 − 4q + q^{2}}{2(1 + q)\sqrt{1 − 6q + q^{2}}} ) C_{0} − \frac{1}{(1 + q)\sqrt{1 − 6q + q^{2}}} = 0.

It follows that

C_{0} = \frac{(1 + q)\sqrt{1 − 6q + q^{2}} − (1 − 4q + q^{2})}{2q(1 − 7q + q^{2})}

(this confirms the conjecture of Fahr and Ringel [1] that \{c_{t}[0]\}, t = 0, 1, 2, … is \underline{A110122} in the On-Line Encyclopedia of Integer Sequences [2]),

that

B_{0} = \frac{3\sqrt{1 − 6q + q^{2}} − (1 + q)}{2(1 − 7q + q^{2})},

(this is the generating function for \underline{A132262} in the On-Line Encyclopedia of Integer Sequences [2]),

and with some work we find that for r ≥ 1,

B_{r} = B_{0} (\frac{β}{4q} )^{r} = B_{0} (\frac{(1 − q)^{2} − (1 + q)\sqrt{1 − 6q + q^{2}}}{8q} )^{r} ,

C_{r} = C_{0} (\frac{β}{4q} )^{r} = C_{0} (\frac{(1 − q)^{2} − (1 + q)\sqrt{1 − 6q + q^{2}}}{8q} )^{r} .

Also, we can confirm the following result of Fahr and Ringel.

Theorem 1.

b_{t}[0] + 3 ∑_{r=1}^{t} 2^{2r−1}b_{t}[r] = F_{4t+2}, 3 ∑_{r=0}^{t} 2^{2r}c_{r}[r] = F_{4t+4},

where the F_{t} are the Fibonacci numbers, given by F_{0} = 0, F_{1} = 1 and F_{t} = F_{t−1} + F_{t−2} for t ≥ 2.

Proof. We have

B_{0} + 3 ∑_{r≥1} 2^{2r−1}B_{r} = B_{0} (1 + 6 (\frac{β}{4q} ) + 24 (\frac{β}{4q} )^{2} + ⋯)

= B_{0} (1 + \frac{6β}{4q(1 − \frac{β}{q})})
= \frac{1 + q}{1 − 7q + q^{2}}
= ∑_{t≥0} F_{4t+2} q^{t}

and

3 ∑_{r≥0} 2^{2r}C_{r} = 3C_{0} (1 + 4 (\frac{β}{4q} ) + 16 (\frac{β}{4q} )^{2} + ⋯)

= 3C_{0} (1 + \frac{β}{q(1 − \frac{β}{q})})
= \frac{3}{1 − 7q + q^{2}}
= ∑_{t≥0} F_{4t+4} q^{t}.

References

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

[2] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, available electronically

   at http://www.research.att.com/~njas/sequences/.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 16G20. Keywords: Partition formula, Fibonacci numbers, recurrences.

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

Received September 3 2009; revised version received October 2 2009. Published in Journal of Integer Sequences, October 2 2009.

Return to Journal of Integer Sequences home page.