On the Binomial Identities of Frisch and Klamkin

H. W. Gould Department of Mathematics West Virginia University Morgantown, WV 26506

USA

henrygou@gmail.com

Jocelyn Quaintance Department of Computer Science

University of Pennsylvania Philadelphia, PA 19104

USA

jocelynq@seas.upenn.edu

Abstract

In this paper we investigate two somewhat similar identities for sums of ratios of binomial coefficients. We give several proofs, and note that the identities all follow from a hypergeometric identity of Gauss. Inverse identities are also given.

1 Introduction

Klamkin [3] stated the following identity in a letter to Gould in 1966:

∑_{k=0}^{n} \begin{matrix}( & {n \atop k} & ) \\ ( & {n+a \atop k+b} & ) \end{matrix} = \frac{a + 1 + n}{(a + 1)\binom{a}{b}}  (1)

Identity (4.6) in Gould’s book [2] is a special case of this, corresponding to a = 2x and b = x. Frisch [1], in his dissertation in 1926, gave the curious formula

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\frac{1}{\binom{b+k}{c}} = \frac{c}{n + c} \frac{1}{\binom{n+b}{b−c}},  b ≥ c > 0.  (2)

This was cited and proved by Netto [4, pp. 337–338] and is tabulated as Formula (4.2) in Gould’s book [2].

(It is interesting to note that Frisch’s research laid the foundations for modern econometrics theory and micro- and macro-economics, work for which he later received the Nobel Prize.)

Klamkin’s identity is actually a special case of the identity

∑_{k=0}^{n} \begin{matrix}( & {n \atop k} & ) \\ ( & {x \atop k+b} & ) \end{matrix} = \frac{x + 1}{(x − n + 1)\binom{x−n}{b}}.  (3)

Here is how we obtain Eq. (3). Let t_{k} = \begin{matrix}( & {n \atop k} & ) \\ ( & {x \atop k+b} & ) \end{matrix}. Then

\frac{t_{k+1}}{t_{k}} = \begin{matrix}\binom{n}{k+1} & \binom{x}{k+b} \\ \binom{x}{k+1+b} & \binom{n}{k} \end{matrix} = \frac{(n − k)(k + 1 + b)}{(k + 1)(x − k − b)}.

Therefore,

∑_{k=0}^{n} \begin{matrix}( & {n \atop k} & ) \\ ( & {x \atop k+b} & ) \end{matrix} = \frac{1}{\binom{x}{b}} _{2}F_{1} [ \begin{matrix}1 + b, & −n \\ −x + b \end{matrix} |1] .  (4)

Applying Gauss’s _{2}F_{1} formula, namely,

2F_{1} [ \begin{matrix}a, & b \\ c \end{matrix} |1] = \frac{Γ(c − a − b)Γ(c)}{Γ(c − a)Γ(c − b)},

we have

∑_{k=0}^{n} \begin{matrix}( & {n \atop k} & ) \\ ( & {x \atop k+b} & ) \end{matrix} = \frac{1}{\binom{x}{b}} · \frac{Γ(−x + n − 1)Γ(−x + b)}{Γ(−x − 1)Γ(−x + b + n)}

= \frac{b!}{x(x − 1) … (x − b + 1)} · \frac{(x + 1)x(x − 1) … (x − n + 3)(x − n + 2)}{(x − b)(x − b − 1) … (x − n − b + 2)(x − n − b + 1)}

= \frac{b!(x + 1) ∏_{j=0}^{n−2}(x − j)}{∏_{j=0}^{n+b−1}(x − j)}

= \frac{b!(x + 1)}{∏_{j=n−1}^{n+b−1}(x − j)}

= \frac{x + 1}{x − n + 1} · \frac{b!}{(x − n)(x − n − 1) … (x − n − b + 1)}

= \frac{x + 1}{x − n + 1} · \frac{1}{\binom{x−n}{b}}.

In this proof we assumed that n ≥ 2. If n = 0, Eq. (1) is obviously true, while if n = 1, we obtain easily verified identity

\frac{1}{\binom{x}{b}} + \frac{1}{\binom{x}{b+1}} = \frac{x + 1}{x\binom{x−1}{b}}.

2 Proof of Klamkin’s and Frisch’s formulas

We shall now prove Klamkin’s formula directly from Formula (7.1) in Gould [2], namely

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\begin{matrix}( & {z \atop k} & ) \\ ( & {y \atop k} & ) \end{matrix} = \begin{matrix}( & {y−z \atop n} & ) \\ ( & {y \atop n} & ) \end{matrix},  (5)

and the easy binomial identity

\binom{x}{k + b}\binom{k + b}{k} = \binom{x}{b}\binom{x − b}{k}  (6)

Indeed, using these we have

∑_{k=0}^{n} \begin{matrix}( & {n \atop k} & ) \\ ( & {x \atop k+b} & ) \end{matrix} = \frac{1}{\binom{x}{b}} ∑_{k=0}^{n} \binom{n}{k}\begin{matrix}( & {k+b \atop k} & ) \\ ( & {x−b \atop k} & ) \end{matrix}

= \frac{1}{\binom{x}{b}} ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\begin{matrix}( & {−1−b \atop k} & ) \\ ( & {x−b \atop k} & ) \end{matrix}

= \frac{1}{\binom{x}{b}} \begin{matrix}( & {x+1 \atop n} & ) \\ ( & {x−b \atop n} & ) \end{matrix} = \frac{x + 1}{(x + 1 − n)\binom{x−n}{b}}

by Formula (7.1), and our proof is complete. We remark that Formula (7.1) is equivalent to using the Gauss _{2}F_{1} formula.

Simple binomial inversion yields the inverse Klamkin identity

∑_{k=0}^{n}(−1)^{n−k}\binom{n}{k}\frac{x + 1}{(x + 1 − k)\binom{x−k}{b}} = \frac{1}{\binom{x}{n+b}}.  (7)

We now proceed in a similar way to prove Frisch’s identity. It is easy to verify the binomial identity

\frac{1}{\binom{k+b}{c}} = \frac{1}{\binom{b}{c}} \begin{matrix}( & {c−b−1 \atop k} & ) \\ ( & {−b−1 \atop k} & ) \end{matrix},

so that

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\frac{1}{\binom{k+b}{c}} = \frac{1}{\binom{b}{c}} ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\begin{matrix}( & {c−b−1 \atop k} & ) \\ ( & {−b−1 \atop k} & ) \end{matrix}.

Upon applying Eq. (5), we find the sum equals

\frac{1}{\binom{b}{c}} \begin{matrix}( & {−c \atop n} & ) \\ ( & {−b−1 \atop n} & ) \end{matrix} = \frac{c}{n + c} \frac{1}{\binom{n+b}{b−c}},

as desired to show.

This new proof of Frisch’s identity should be compared to Gould’s original proof [5, Section 7.2], a two-page calculation involving an application of Melzak’s formula.

An inverse Frisch identity then follows by simple binomial inversion, and we have

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\frac{c}{k + c} \frac{1}{\binom{k+b}{b−c}} = \frac{1}{\binom{n+b}{c}}.  (8)

References

[1] Ragnar Frisch, Sur les semi-invariants et moments employés dans l’étude des distributions statistiques, Skrifter utgitt av Det Norske Videnskaps-Akademi i Oslo, II, Historisk-Filosofisk Klasse 3 (1926), 1–87. Quoted by Th. Skolem, p. 337, in Netto’s Lehrbuch.

[2] H. W. Gould, Combinatorial Identities, published by the author, Morgantown, WV, 1972.

[3] Murray S. Klamkin, Letter to H. W. Gould, May 16, 1966.

[4] Eugen Netto, Lehrbuch der Kombinatorik, 2nd edition, Chelsea Publications, 1927.

[5] Jocelyn Quaintance and H. W. Gould, Combinatorial Identities for Stirling Numbers, World Scientific Press, 2016.

2010 Mathematics Subject Classification: Primary 05A19; Secondary 11B65, 33C10. Keywords: binomial identity, hypergeometric series, Gauss’ hypergeometric summation formula, binomial inversion.

Received July 4 2016; revised versions received August 31 2016; September 1 2016; September 7 2016. Published in Journal of Integer Sequences, September 7 2016.

Return to Journal of Integer Sequences home page.