INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A02

A BIJECTIVE PROOF OF f_{n+4} + f_{1} + 2f_{2} + ⋯ + nf_{n} = (n + 1)f_{n+2} + 3

Philip Matchett Wood

Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd, Piscataway, NJ 08854-8019, USA

                         matchett@math.rutgers.edu

Received: 10/6/05, Revised: 1/5/06, Accepted: 1/16/06, Published: 2/1/06

Abstract

In Proofs that Really Count, Benjamin and Quinn mentioned that there was no known bijective proof for the identity f_{1} + 2f_{2} + ⋯ + nf_{n} = (n + 1)f_{n+2} − f_{n+4} + 3 for n ≥ 0, where f_{k} is the k-th Fibonacci number. In this paper, we interpret f_{k} as the cardinality of the set F_{k} consisting of all ordered lists of 1’s and 2’s whose sum is k. We then demonstrate a bijection between the sets F_{n+4} ∪ ⋃_{k=1}^{n} ({1, 2, …, k} × F_{k}) and ({1, 2, …, n + 1} × F_{n+2}) ∪ {1, 2, 3}, which gives a bijective proof of the identity.

1. Introduction

We will interpret the k-th Fibonacci number f_{k} as the cardinality of the set F_{k} of all ordered lists of 1’s and 2’s that have sum k. Thus, (f_{0}, f_{1}, f_{2}, f_{3}, f_{4}, f_{5}, …) = (1, 1, 2, 3, 5, 8, …). For an integer m, the number mf_{k} will be interpreted as the cardinality of the Cartesian product [m] × F_{k}, where [m] := {1, 2, 3, …, m}.

On page 14 of Proofs that Really Count [1], Benjamin and Quinn mentioned that there was no known bijective proof for the identity f_{1} + 2f_{2} + … + nf_{n} = (n + 1)f_{n+2} − f_{n+4} + 3 for n ≥ 0. In Section 2 we define a map

ϕ : F_{n+4} ∪ ⋃_{k=1}^{n} ([k] × F_{k}) ⟶ {1, 2, 3} ∪ ([n + 1] × F_{n+2}) ,

and in Section 3 we describe why ϕ is a bijection. This provides a bijective proof of the identity f_{n+4} + f_{1} + 2f_{2} + … + nf_{n} = (n + 1)f_{n+2} + 3 for n ≥ 0. For completeness, we also define the inverse map

ψ : {1, 2, 3} ∪ ([n + 1] × F_{n+2}) ⟶ F_{n+4} ∪ ⋃_{k=1}^{n} ([k] × F_{k})

in Section 4, and the cases in the definition of ψ correspond to those for ϕ.

When examples are given below, ordered lists are denoted using angled brackets, e.g., ⟨a_{1}, a_{2}, …, a_{m}⟩. Also, Doron Zeilberger [4] has written a Maple package that implements the bijection, which may be downloaded from

            http://www.math.rutgers.edu/∼zeilberg/tokhniot/PHIL  (1)

2. The bijection ϕ

In this section we define the bijection

ϕ : F_{n+4} ∪ ⋃_{k=1}^{n}([k] × F_{k}) ⟶ {1, 2, 3} ∪ ([n + 1] × F_{n+2}).

For X ∈ F_{n+4} where the last n numbers in the list X are 1’s, define ϕ according to the chart below.

\begin{matrix}ϕ : & ⟨1, 1, 1, 1, & \overbrace{1, 1, …, 1}^{n}⟩ & ↦ & (1, ⟨\overbrace{1, 1, …, 1}^{n+2}⟩) \\ ϕ : & ⟨2, 1, 1, & \overbrace{1, 1, …, 1}^{n}⟩ & ↦ & 1 \\ ϕ : & ⟨1, 2, 1, & \overbrace{1, 1, …, 1}^{n}⟩ & ↦ & 2 \\ ϕ : & ⟨1, 1, 2, & \overbrace{1, 1, …, 1}^{n}⟩ & ↦ & 3 \\ ϕ : & ⟨2, 2, & \overbrace{1, 1, …, 1}^{n}⟩ & ↦ & (1, ⟨2, \overbrace{1, 1, …, 1}^{n}⟩) \end{matrix}

For all cases not covered by the chart above, we define ϕ by the two cases below.

Case 1: Consider X ∈ F_{n+4}, so X is a list of 1’s and 2’s that sums to n + 4. By the above special cases above, we know that X ends in a string of exactly ℓ 1’s, where 0 ≤ ℓ < n (so X has a 2 followed by ℓ 1’s at the end). Take X and delete the last 2 in X to get X̂, which is an element of F_{n+2}, and define ϕ : X ↦ (n − ℓ + 1, X̂).

Examples for n = 3:

\begin{matrix}ϕ : & ⟨1, 1, 2, 1, 2⟩ & ↦ & (4, ⟨1, 1, 2, 1⟩) \\ ϕ : & ⟨1, 1, 2, 2, 1⟩ & ↦ & (3, ⟨1, 1, 2, 1⟩) \\ ϕ : & ⟨1, 1, 1, 2, 1, 1⟩ & ↦ & (2, ⟨1, 1, 1, 1, 1⟩) \end{matrix}

Case 2: Consider (i, X) where X ∈ F_{k} and i ∈ [k] (and thus i ≤ k). Take X and append a 2 followed by (n − k) 1’s to get X̃, which is an element of F_{n+2}, and define ϕ : (i, X) ↦ (i, X̃).

Examples for n = 3:

\begin{matrix}ϕ : & (1, ⟨1⟩) & ↦ & (1, ⟨1, 2, 1, 1⟩) \\ ϕ : & (1, ⟨1, 1⟩) & ↦ & (1, ⟨1, 1, 2, 1⟩) \\ ϕ : & (2, ⟨2⟩) & ↦ & (2, ⟨2, 2, 1⟩) \\ ϕ : & (2, ⟨2, 1⟩) & ↦ & (2, ⟨2, 1, 2⟩) \end{matrix}

3. Showing ϕ is bijective

The following three facts (which may be easily verified) help show that ϕ is injective:

1. The image of ϕ from the five special cases consists of {1, 2, 3} and all elements (i, Y) of [n + 1] × F_{n+2} where i = 1 and Y ends in at least n = (n + 1 − i) 1’s.

2. The image of ϕ from Case 1 consists of all elements (i, Y) of [n + 1] × F_{n+2} where 2 ≤ i ≤ n + 1 and Y ends in at least (n + 1 − i) 1’s.

3. The image of ϕ from Case 2 consists of all elements (i, Y) of [n + 1] × F_{n+2} where 1 ≤ i ≤ n and one of the last (n + 1 − i) entries in Y is a 2.

It is easily seen from the definition that ϕ restricted to Case 1 is injective; and similarly, ϕ is injective when restricted to Case 2 or to the five special cases. Thus, since the three images described above are distinct, ϕ as a whole is injective. Furthermore, the union of the three images above consists of all of {1, 2, 3}∪([n + 1] × F_{n+2}) (note that there is no element (i, Y) ∈ [n + 1] × F_{n+2} with i = n + 1 and Y containing a 2 in the last (n + 1 − i) entries). Thus ϕ is a bijection.

4. The inverse bijection ψ

In this section we define the inverse bijection

ψ : {1, 2, 3} ∪ ([n + 1] × F_{n+2}) ⟶ F_{n+4} ∪ ⋃_{k=1}^{n}([k] × F_{k}).

For elements of \{1, 2, 3\} and for the elements (1, ⟨\overbrace{1, 1, …, 1}^{n+2}⟩) and (1, ⟨2, \overbrace{1, 1, …, 1}^{n}⟩) of [n + 1] × F_{n+2}, define ψ according to the chart below.

\begin{matrix}ψ : & (1, ⟨\overbrace{1, 1, …, 1}^{n+2}⟩) & ↦ & ⟨1, 1, 1, 1, & \overbrace{1, 1, …, 1}^{n}⟩ \\ ψ : & 1 & ↦ & ⟨2, 1, 1, & \overbrace{1, 1, …, 1}^{n}⟩ \\ ψ : & 2 & ↦ & ⟨1, 2, 1, & \overbrace{1, 1, …, 1}^{n}⟩ \\ ψ : & 3 & ↦ & ⟨1, 1, 2, & \overbrace{1, 1, …, 1}^{n}⟩ \\ ψ : & (1, ⟨2, \overbrace{1, 1, …, 1}^{n}⟩) & ↦ & ⟨2, 2, & \overbrace{1, 1, …, 1}^{n}⟩ \end{matrix}

For all cases not covered by the chart above, we define ψ as follows. Consider (i, Y), where Y ∈ F_{n+2} and i ∈ [n + 1].

Case 1: If Y ends with at least (n + 1 − i) 1’s, then insert a 2 before the last (n + 1 − i) 1’s to get Ỹ and define ψ : (i, Y) ↦ Ỹ.

Examples for n = 3:

\begin{matrix}ψ : & (4, ⟨1, 1, 1, 2⟩) & ↦ & ⟨1, 1, 1, 2, 2⟩ \\ ψ : & (3, ⟨2, 1, 1, 1⟩) & ↦ & ⟨2, 1, 1, 2, 1⟩ \\ ψ : & (2, ⟨1, 1, 1, 1, 1⟩) & ↦ & ⟨1, 1, 1, 2, 1, 1⟩ \end{matrix}

Case 2: If one of the last n + 1 − i entries in Y is a 2, then delete the last 2 in Y and all 1’s following that 2 to get Ŷ. Define ψ : (i, Y) ↦ (i, Ŷ).

Examples for n = 3:

\begin{matrix}ψ : & (1, ⟨1, 2, 1, 1⟩) & ↦ & (1, ⟨1⟩) \\ ψ : & (1, ⟨1, 1, 2, 1⟩) & ↦ & (1, ⟨1, 1⟩) \\ ψ : & (2, ⟨2, 2, 1⟩) & ↦ & (2, ⟨2⟩) \\ ψ : & (2, ⟨2, 1, 2⟩) & ↦ & (2, ⟨2, 1⟩) \end{matrix}

Acknowledgements The author would like to thank Doron Zeilberger for suggesting this problem and for providing valuable support in solving it. Thanks also is due to the anonymous referee for helpful comments in revising and polishing this paper.

References

[1] Benjamin, A.T.; Quinn, J.J.. Proofs that Really Count—the art of combinatorial proof. The Dolciani Mathematical Expositions, 27. Mathematical Association of America, Washington, DC, 2003.

[2] Benjamin, A.T.; Quinn, J.J.. The Fibonacci numbers—exposed more discretely. Math. Mag. 76 (2003), no. 3, 182–192.

[3] Benjamin, A.T.; Quinn, J.J.; Su, F.E.. Phased tilings and generalized Fibonacci identities. Fibonacci Quart. 38 (2000), no. 3, 282–288.

[4] Zeilberger, D.. Maple implementation of the bijection. http://www.math.rutgers.edu

   /∼zeilberg/tokhniot/PHIL. December 9, 2005.