Generating Function for the Reciprocals of the Central Binomial Coefficients

In this post we generalize the result from the last post to find the generating function for the reciprocals of the central binomial coefficients.  As we did with that one, we start with the beta integral expression for 1/\binom{2n}{n}:

\displaystyle \frac{1}{\binom{2n}{n}} = (2n+1) \int_0^1 y^n (1-y)^n \, dy = \int_0^1 (2n+1) (y(1-y))^n \, dy.

Now, multiply by \frac{x^n}{2n+1} (for now, it’s easier not to deal with the extra factor of 2n+1 on the right) and sum up:

\displaystyle \sum_{n=0}^{\infty} \frac{x^n}{\binom{2n}{n} (2n+1)} = \sum_{n=0}^{\infty} \int_0^1 (xy(1-y))^n \, dy = \int_0^1 \left( \sum_{n=0}^{\infty}  (xy(1-y))^n \right) \, dy = \int_0^1 \frac{1}{1-xy(1-y)} \, dy,

where we use the geometric series formula in the last step.  Now, apply the substitution t = \sqrt{x} (2y-1).  It’s not obvious at this point that this will be helpful, but it will.  The denominator of the integral becomes

\displaystyle 1-xy(1-y) = 1-x \left(\frac{t + \sqrt{x}}{2\sqrt{x}}\right) \left( \frac{\sqrt{x}-t}{2 \sqrt{x}}\right) = 1- \frac{x-t^2}{4} = \frac{4 - x+ t^2}{4}.

This gives us

\displaystyle \int_0^1 \frac{1}{1-xy(1-y)} \, dy = \int_{-\sqrt{x}}^{\sqrt{x}} \frac{4}{2 \sqrt{x} (t^2 + 4-x)} \, dt = \frac{2}{\sqrt{x}} \int_{-\sqrt{x}}^{\sqrt{x}} \frac{1}{t^2 + 4-x} \, dt \\  = \left.\frac{2}{\sqrt{x (4-x)}} \arctan \left( \frac{t}{\sqrt{4-x}} \right) \right|_{-\sqrt{x}}^{\sqrt{x}} \\  = \frac{2}{\sqrt{4x-x^2}} \left( \arctan \left( \frac{\sqrt{x}}{\sqrt{4-x}} \right) - \arctan \left( \frac{-\sqrt{x}}{\sqrt{4-x}} \right) \right)\\  = \frac{4}{\sqrt{4x-x^2}} \arctan \left( \frac{\sqrt{x}}{\sqrt{4-x}} \right) \\  = \frac{4}{\sqrt{4x-x^2}} \arcsin \left( \frac{\sqrt{x}}{2} \right),

where in the second-to-last step we use the fact that arctangent is an odd function.

In sum, we now have

\displaystyle \sum_{n=0}^{\infty} \frac{x^n}{\binom{2n}{n} (2n+1)} = \frac{4}{\sqrt{4x-x^2}} \arcsin \left( \frac{\sqrt{x}}{2} \right).

We have some more work to do to get the left side where we want it.  Replace x with x^2 to get

\displaystyle \sum_{n=0}^{\infty} \frac{x^{2n}}{\binom{2n}{n} (2n+1)} = \frac{4}{\sqrt{4x^2-x^4}} \arcsin \left( \frac{x}{2} \right) =  \frac{4}{x\sqrt{4-x^2}} \arcsin \left( \frac{x}{2} \right) .

(Technically, we get |x| in place of x on the right, but since arcsine is odd the expression simplifies to what we have here.)  Now, multiply both sides by x and differentiate.  After some simplification, we get the following:

\displaystyle \sum_{n=0}^{\infty} \frac{x^{2n}}{\binom{2n}{n}} =  \frac{1}{1-\left(\frac{x}{2}\right)^2} + \frac{4x \arcsin \left(\frac{x}{2}\right)}{(4-x^2)^{3/2}}.

To finish, we replace x with \sqrt{x}:

\displaystyle \sum_{n=0}^{\infty} \frac{x^{2n}}{\binom{2n}{n}} =  \frac{1}{1-\frac{x}{4}} + \frac{4 \sqrt{x}\arcsin \left(\frac{\sqrt{x}}{2}\right)}{(4-x)^{3/2}}.

(To verify with the result from the previous post, we need to investigate this result for convergence.  Convergence matters only with the geometric series evaluation with common ratio xy(1-y).  Since y must be between 0 and 1, the max value of y(1-y) is 1/4, and so the values of x for which the series converges are -4 < x < 4.  Thus we can safely substitute 1 for x in the formula we just derived, obtaining \frac{4}{3} + \frac{2 \pi \sqrt{3}}{27}, as we found in the last post.)


Posted in binomial coefficients, generating functions, sequences and series | Leave a comment

Sum of the Reciprocals of the Central Binomial Coefficients

In this post we prove the formula for the sum of the reciprocals of the central binomial coefficients \binom{2n}{n}:

\displaystyle \sum_{n=0}^{\infty} \frac{1}{\binom{2n}{n}} = \frac{4}{3}  + \frac{2 \pi \sqrt{3}}{27}.

(Of course, the sum of the central binomial coefficients themselves does not converge.)

We start with the beta integral\displaystyle \frac{1}{\binom{n}{k}} = (n+1) \int_0^1 x^k (1-x)^{n-k} \, dx.

Replacing n with 2n and k with n, this becomes

\displaystyle \frac{1}{\binom{2n}{n}} = (2n+1) \int_0^1 x^n (1-x)^n \, dx = \int_0^1 (2n+1) (x(1-x))^n \, dx.

Now, let y = \sqrt{x(1-x)} and sum both sides from 0 to \infty, moving the summation inside the integral.  (We’re not performing a u-substitution here; the bounds and the differential remain in terms of x.  The substitution is just to make the upcoming infinite series calculation easier to see.)  We have

\displaystyle \sum_{n=0}^{\infty} \frac{1}{\binom{2n}{n}} = \int_0^1 \sum_{n=0}^{\infty} (2n+1) y^{2n} \, dx = \int_0^1 \sum_{n=0}^{\infty}  \frac{d}{dy} (y^{2n+1}) \, dx = \int_0^1 \frac{d}{dy} \sum_{n=0}^{\infty}   y^{2n+1} \, dx

\displaystyle = \int_0^1  \frac{d}{dy} \left( y \sum_{n=0}^{\infty}  (y^2)^n \right) \, dx = \int_0^1 \frac{d}{dy} \left( \frac{y}{1-y^2} \right) \, dx = \int_0^1 \frac{1+y^2}{(1-y^2)^2} dx

\displaystyle = \int_0^1 \frac{1+x-x^2}{(1-x+x^2)^2} dx.

(The infinite series \sum_{n=0}^{\infty} (y^2)^n converges because x must be between 0 and 1, which means the maximum value of y = \sqrt{x(1-x)} is 1/2.)

At this point we have the integral of a rational function.  Partial fractions decomposition (or just rewriting the numerator as 2 - (1-x+x^2)) gets us to

\displaystyle \int_0^1 \left(\frac{-1}{(1-x+x^2)^2} + \frac{2}{(1-x+x^2)^2}\right)  dx.

Using trigonometric substitution, this evaluates to

\displaystyle \left. \frac{2\sqrt{3}}{9} \arctan \left( \frac{2x-1}{\sqrt{3}} \right) + \frac{2(2x-1)}{3(1-x+x^2)} \right|_0^1

\displaystyle = \frac{2\sqrt{3}}{9} \arctan \frac{1}{\sqrt{3}} + \frac{2}{3} - \frac{2 \sqrt{3}}{9} \arctan \left(\frac{-1}{\sqrt{3}}\right) - \frac{-2}{3}

\displaystyle = \frac{4}{3} + \frac{2\sqrt{3}}{9} \left( \frac{\pi}{6} - \frac{-\pi}{6} \right) = \frac{4}{3} + \frac{2\pi \sqrt{3}}{27}.

Posted in binomial coefficients, sequences and series | 1 Comment

A Probabilistic Proof of a Binomial Coefficient Identity, Generalized

In a post from a couple of years ago I gave a probabilistic proof of the binomial coefficient identity

\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{k+1} = \frac{1}{n+1}.

In this post I modify and generalize this proof to establish the identity

\displaystyle (1) \:\:\:\:\:\: \sum_{k=0}^n \frac{(-1)^k}{m+k} = \frac{(m-1)! \, n!}{(m+n)!}.

As in the original proof, we use a balls-and-jars interpretation.  Suppose we have a jar that contains a black ball, n numbered blue balls, and m-1 numbered red balls.  Suppose we choose the balls one-by-one from the jar.  Let A_i be the event that the black ball is chosen after blue ball i.  Let B be the event that the black ball is chosen before all the red balls.  We argue that Identity (1) gives in two different ways the probability of B \cap \bigcap_{i=1}^n A_i, the event that all the blue balls are chosen, then the black ball, and then all the red balls.

The right side of Identity (1) is easier to explain.  There are (m+n)! ways to arrange all m+n balls.  There are (m-1)! ways to order the blue balls, one way to order the black ball, and n! ways to order the red balls.  This gives \displaystyle \frac{(m-1)! \, n!}{(m+n)!} as the probability that all the blue balls are selected, then the black ball, and then all of the red balls.

For the left side of Identity (1) we need the principle of inclusion/exclusion.  A slight generalization of one version of it says that

\displaystyle P \left(B \cap \bigcap_{i=1}^n A_i \right) = P(B) - \sum_{i=1}^n P(B \cap \bar{A}_i) + \sum_{1 \leq i < j \leq n} P(B \cap \bar{A}_i \cap \bar{A}_j) \\ - \sum_{1 \leq i < j < k \leq n} P(B \cap \bar{A}_i \cap \bar{A}_j \cap \bar{A}_k) + \cdots + (-1)^n P(B \cap \bar{A}_1 \cap \cdots \cap \bar{A}_n).

The event \bar{A}_i is the event that the black ball is chosen before blue ball i.  Thus, the intersection of any k of these \bar{A}_i‘s with B is the event that the black ball is chosen first out of m+k specific balls: the black one, the m-1 red ones, and k of the blue ones.  This has probability 1/(m+k).  There are \binom{n}{k} ways to select k of the \bar{A}_i‘s.  By this generalized inclusion/exclusion principle, then, the probability that the black ball is chosen after the blue balls but before any of the red balls is also given by

\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{m+k}.

This argument is taken from my paper [1], where I give a probabilistic proof of the binomial inverse of Identity (1), as well as proofs of generalizations of both (1) and its binomial inverse.


  1.  Michael Z. Spivey, “Probabilistic proofs of a binomial identity, its inverse, and generalizations.” American Mathematical Monthly, 123 (2): 175-180, 2016.
Posted in binomial coefficients, probability | Leave a comment

A Proof of Dobinski’s Formula for Bell Numbers

Dobinski’s formula entails the following infinite series expression for the nth Bell number \varpi_n:

\displaystyle \varpi_n = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!}.

In this post we’ll work through a proof of Dobinski’s formula.  We’ll need four formulas:

  1. The Maclaurin series for e^x: \displaystyle e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}.
  2. The formula for converting normal powers to falling factorial powers: \displaystyle x^n = \sum_{k=0}^n \left\{ n \atop k \right\} x^{\underline{k}}, where \left\{ n \atop k \right\} is a Stirling number of the second kind.
  3. The formula relating Bell numbers and Stirling numbers of the second kind: \displaystyle \varpi_n = \sum_{k=0}^n \left\{ n \atop k \right\}.  (This follows directly from the combinatorial definitions of the Bell numbers and the Stirling numbers of the second kind.)
  4. The representation of falling factorial powers as factorials: \displaystyle k^{\underline{m}} = \frac{k!}{(k-m)!}, valid when k \geq m and k, m \in \mathbb{N}.

Here we go… Starting with the infinite series expression \displaystyle \sum_{k=0}^{\infty} \frac{k^n}{k!}, convert to falling factorial powers to get

\displaystyle \sum_{k=0}^{\infty} \frac{k^n}{k!} = \sum_{k=0}^{\infty} \frac{1}{k!} \sum_{j=0}^n \left\{n \atop j \right\} k^{\underline{j}} = \sum_{j=0}^n \left\{ n \atop j \right\} \sum_{k=0}^{\infty} \frac{k^{\underline{j}}}{k!} = \sum_{j=0}^n \left\{n \atop j \right\} \sum_{k=j}^{\infty} \frac{k^{\underline{j}}}{k!} = \sum_{j=0}^n \left\{ n \atop j \right\} \sum_{k=j}^{\infty} \frac{1}{(k-j)!} = \sum_{j=0}^n \left\{ n \atop j \right\} \sum_{i=0}^{\infty} \frac{1}{i!} = \sum_{j=0}^n \left\{ n \atop j \right\} e.

Thus \displaystyle \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!} = \frac{1}{e} \sum_{j=0}^n \left\{ n \atop j \right\} e = \varpi_n.

(I made a similar argument in this Math.SE question.)

Posted in Bell numbers, sequences and series, Stirling numbers | Leave a comment

Operations Research Makes List of Top 5 STEM Professions Employing Women

My February 2016 issue of ORMS Today says that “operations research analyst” is the STEM (Science, Technology, Engineering, and Mathematics) profession with the third-highest percentage of women.  The percentage of OR analysts who are women is 55.4%.  I’m glad to see that, and I’m not that surprised, given what I’ve seen in the profession.

The sentence that caught my eye, though, was this one: “This field only has 55.4 percent female workers, but that is still a considerable amount when looking at women in STEM.”  Only 55.4%?  What I think they mean is that for the STEM profession with the third-highest percentage of women, that’s a relatively small number.  But it sure looks funny to say “only,” which seems to imply that 55.4% is somehow not a large enough percentage of women.  (Would 44.6% men be too many?)

ORMS Today gives the source as the January 12, 2016, edition of USA Today.  I couldn’t find that online, but I did find this site that gives the same text quoted in ORMS Today.

A couple of pages later, in the “Newsmakers” section, ORMS Today says that, “According to [MIT Professor Richard] Larson, people can expect to spend one to two years of their lives waiting line, most of it stuck in traffic.”  Yikes!


Posted in optimization, statistics, operations research, gender | Leave a comment

An Explicit Solution to the Fibonacci Recurrence

The Fibonacci sequence is a famous sequence of numbers that starts 1, 1, 2, 3, 5, 8, 13, 21, and continues forever.  Each number in the sequence is the sum of the two previous numbers in the sequence.  It’s easy to generate the sequence this way, but if you want, say, the 1000th Fibonacci number, it’s going to take you a while to get there by hand.  In this post I’m going to discuss how to come up with a formula for the nth Fibonacci number.

Let’s let F_n denote the nth Fibonacci number.  Let’s start counting with n = 0, and say F_0 = 0.  Then F_1 = 1.  These are known as the initial conditions. For n \geq 2, F_n = F_{n-1} + F_{n-2}.  This is known as the recurrence.

The first thing I want to prove is that the set of solutions to the Fibonacci recurrence F_n = F_{n-1} + F_{n-2} (ignoring the initial conditions for now) form what’s called a vector space (under function addition and scalar multiplication).  To show that a set is a vector space we need to show that it satisfies a particular collection of axioms.  Suppose the sequence \{s_n\} is a solution to the Fibonacci recurrence.  Most of the vector space axioms are satisfied simply because s_n is a function; the ones we still need to check are that (1) adding two solutions gives us another solution, and (2) multiplying a solution by a constant (a scalar) gives us another solution.  First, if s_n and t_n are solutions, then substituting s_n + t_n for F_n in the right side of the recurrence yields (s_{n-1} + t_{n-1}) + (s_{n-2} + t_{n-2}) = (s_{n-1} + s_{n-2}) + (t_{n-1} + t_{n-2}) = s_n + t_n, which proves that s_n + t_n is also a solution to the Fibonacci recurrence.  Second, if s_n is a solution and c is a constant then substituting cs_n into the right side of the recurrence yields cs_{n-1} + cs_{n-2} = c(s_{n-1} + s_{n-2}) = cs_n, which means that c s_n is also a solution to the recurrence.  Thus (1) and (2) are satisfied, which means that the set of solutions to the Fibonacci recurrence is a vector space.  (Again, we’re ignoring the initial conditions.)

This may seem like a lot of overhead, but there’s a good reason. Vector spaces have something called a dimension.  (Example: Real Euclidean three-space \mathbb{R}^3 has dimension 3.)  The vector space consisting of the solutions to the Fibonacci recurrence turns out to have dimension 2.  (See below.)  Because of this, if we can find two solutions s_n and t_n to the Fibonacci recurrence that are not simply multiples of each other (more generally, are not linearly independent), then every solution to the Fibonacci recurrence must be of the form p s_n + q t_n, where p and q are some constants that depend on the initial conditions.  The set \{s_n, t_n\} is called a basis of the solution space.

Let’s now see why the dimension of the solution space to the Fibonacci recurrence is 2. We can represent the Fibonacci recurrence in matrix form like so: \displaystyle \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix}.  If we let X_n = (F_n, F_{n-1}) and A denote the matrix, this equation becomes X_n = A X_{n-1}.  Since the transition matrix A has dimension 2, so does the vector space of solutions to the Fibonacci recurrence.

Now we just need to find two solutions to the Fibonacci recurrence that aren’t multiples of each other.  Going simpler, the recurrence S_n = 2 S_{n-1} has S_n = 2^n as a solution.  Since the Fibonacci recurrence can be represented just like this, X_n = A X_{n-1}, with the matrix A instead of 2 and a vector X_n instead of S_n, maybe there is also a solution to the Fibonacci recurrence of the form F_n = r^n.  We just need to figure out the value of r.  So let’s substitute F_n = r^n into the Fibonacci recurrence and see if there are any values of r that work.  We get r^n = r^{n-1} + r^{n-2}. Dividing by r^{n-2}, we end up with r^2 = r + 1.  Solving this equation with the quadratic formula, we get not one but two values for r: \displaystyle r_1 = \frac{1 + \sqrt{5}}{2}, and \displaystyle r_2 = \frac{1 - \sqrt{5}}{2}.  This means that s_n = r_1^n and t_n = r_2^n are both solutions to the Fibonacci recurrence.  And since these solutions are not multiples of each other, they can be our set of basis solutions!

This means that every solution to the Fibonacci recurrence must be of the form  F_n = p r_1^n + q r_2^n, where r_1 = \frac{1 + \sqrt{5}}{2} and r_2 = \frac{1 - \sqrt{5}}{2}.  The specific solution we want is the one that has values for p and q such that the initial conditions F_0 = 0 and F_1 = 1 are satisfied.  Plugging n = 0 and n = 1 into F_n = p r_1^n + q r_2^n, we have 0 = p + q and 1 = p r_1 + q r_2.  Using the fact that r_1 + r_2 = 1, we can solve this system of equations to find out that p = 1/\sqrt{5}, q = -1/\sqrt{5}.  Therefore, the explicit solution to the Fibonacci recurrence is

\displaystyle F_n = \frac{1}{\sqrt{5}} \left(\frac{1 + \sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}} \left(\frac{1 - \sqrt{5}}{2}\right)^n.

This formula is known as Binet’s formula.

Additional comments:

  1. The number r_1 = \frac{1+\sqrt{5}}{2} is known as the golden ratio.
  2. The number r_2 = \frac{1-\sqrt{5}}{2} is between -1 and 0, which means that as n gets larger and larger r_2^n gets closer and closer to 0.  Thus, for large values of n, F_n \approx \frac{1}{\sqrt{5}} r_1^n.
  3. The technique described here can be used to solve any linear homogeneous recurrence relation with constant coefficients.
Posted in Fibonacci sequence, recurrence relations, sequences and series | Leave a comment

Calculating SECA Offsets for Clergy

Recently my pastor posed a problem to me: How to calculate his SECA offset?  The answer can be found using algebra or using infinite series.  (For the non-math inclined, skip to the bottom of this post for an answer.)

Background: Most of us who work for an organization in the United States are charged a 15.3% Social Security FICA tax.  (This is 15.3% of our salaries.)  Half (7.65%) of that tax is paid by our employers, and the other half is paid by us (in the form of a deduction from our paychecks).  However, clergy are considered self-employed for Social Security tax purposes, which means that they have to pay all 15.3% themselves.  To counteract this, many congregations pay their clergy an extra 7.65% of their compensation to cover the Social Security tax that is normally covered by employers.  This is called a SECA offset.  However, this extra bit is itself considered compensation, so it is also taxed by Social Security!  This means that the SECA offset payment, if it is calculated this way, is actually less than needed to cover the intended part of the clergy’s Social Security tax.  The congregation could then pay an extra part to make up that difference, but that extra part would also be taxed, which means they’re still underpaying… and so on forever, in a perpetual cycle.

Let’s take an example.  Suppose a pastor makes a nice, round $50,000 in compensation.  On top of this, the congregation pays the pastor a SECA offset of 7.65%, which is $3825.  This means the pastor’s actual taxable income from the church is $53,825.  The 7.65% Social Security tax on $53,825 is $4117.61, which means the congregation has actually underpaid by $4117.61 minus $3825, which is $292.61.  The congregation could then give the extra $292.61 to the pastor, but that would itself count as income and thus raise the pastor’s Social Security tax even further.  Again, this process could continue forever.  Fortunately, looking at this problem the right way mathematically can solve it for us.

Let’s formulate the problem like this: How much should a congregation pay its clergy in SECA offset if it wants that payment to be exactly 7.65% of the clergy’s total compensation?

(Infinite Series Solution.)  Turning to math, let’s let A denote a pastor’s original compensation.  The first-order attempt at covering the SECA offset is 0.0765A.  This, though, is taxable, so the congregation needs to include 7.65% of this amount, or (0.0765)^2 A.  But then this extra is also taxable at 7.65%, so the congregation needs to include an additional (0.0765)^3 A, and so on.  Continuing in this vein, we have what is known as an infinite series for the amount the congregation should pay the pastor in total compensation:

\displaystyle A + 0.0765 A + (0.0765)^2 A + (0.0765)^3 A + (0.0765)^4 A + (0.0765)^5 A + \cdots.

The shorthand way to write an infinite series like this one is with sigma notation:

\displaystyle \sum_{i=0}^{\infty} (0.0765)^i A = A \sum_{i=0}^{\infty} (0.0765)^i.

This infinite series is a special class of infinite series known as a geometric series, \displaystyle \sum_{i=0}^{\infty} r^i.  In our example, r = 0.0765.  Provided -1 < r < 1, geometric series satisfy the nice formula

\displaystyle \sum_{i=0}^{\infty} r^i = \frac{1}{1-r}.

This gives us our answer: The congregation should pay the pastor a total of

\displaystyle A \sum_{i=0}^{\infty} (0.0765)^i = \frac{A}{1-0.0765} = \frac{A}{0.9235} = 1.082837A.  Subtracting the original compensation of A from this, we’re left with 0.082837A for the SECA offset.

This means the SECA offset should actually be 8.2837% of the original compensation if that payment is to be exactly 7.65% of the clergy’s total compensation.

(Algebra Solution.)  While the infinite series solution is the straightforward way of tackling the problem, the math is much easier if we set up an algebraic equation to solve the problem.  Let’s let x denote the desired amount of SECA offset, with A the pastor’s original compensation.  We want x to be exactly 7.65% of the pastor’s total compensation.  The pastor’s total compensation, though, is A+x.  That gives us the following equation:

x = 0.0765(A+x) .

Solving this for x, we get x = 0.0765A + 0.0765x, or 0.9235x = 0.0765A, or x = \frac{0.0765}{0.9235}A = 0.082837A, the same answer as before – but with less work.

(Of course, in practice there are other issues to consider, such as the fact that raising the pastor’s compensation by 8.2837% will raise his/her income tax and benefit payments as well.  The answer to the problem as posed, though, which just focuses on the SECA offset, is 8.2837% of the original compensation amount.)

Posted in applications, sequences and series | Leave a comment