Home » Binomial Coefficients

Tag: Binomial Coefficients

Prove some properties of binomial coefficients of a real number α

by RoRi

The binomial coefficient \binom{\alpha}{n} is defined by

    \[ \binom{\alpha}{n} = \frac{\alpha(\alpha - 1)(\alpha - 2) \cdots (\alpha - n + 1)}{n!} \]

where \alpha \in \mathbb{R} and n \in \mathbb{Z}_{\geq 0}.

  1. For \alpha = -\frac{1}{2} show that

        \[ \binom{\alpha}{1} = -\frac{1}{2}, \quad \binom{\alpha}{2} = \frac{3}{8}, \quad \binom{\alpha}{3} = -\frac{5}{16}, \quad \binom{\alpha}{4} = \frac{35}{128}, \quad \binom{\alpha}{5} = -\frac{63}{256}. \]

  2. Consider the series whose terms are defined by

        \[ a_n = (-1)^n \binom{-\frac{1}{2}}{n}. \]

    Prove that

        \[ a_n > 0 \qquad \text{and} \qquad a_{n+1} < a_n. \]

  1. We compute each of the requested quantities using the given definition, where \alpha = -\frac{1}{2},

        \begin{align*} \binom{\alpha}{1} &= \binom{-\frac{1}{2}}{1} = \frac{-\frac{1}{2}}{1} = -\frac{1}{2}. \\[10pt] \binom{\alpha}{2} &= \binom{-\frac{1}{2}}{2} = \left(-\frac{1}{2}\right)\left(-\frac{3}{\frac{2}{2}}\right) = \frac{3}{8}. \\[10pt] \binom{\alpha}{3} &= \binom{-\frac{1}{2}}{3} = \left( \frac{3}{8} \right) \left( \frac{-\frac{5}{2}}{3} \right) = -\frac{5}{16} \\[10pt] \binom{\alpha}{4} &= \binom{-\frac{1}{2}}{4} = \left(-\frac{5}{16} \right) \left( \frac{-\frac{7}{2}}{4} \right) = \frac{35}{128} \\[10pt] \binom{\alpha}{5} &= \binom{-\frac{1}{2}}{5} = \left( \frac{35}{128} \right) \left( \frac{-\frac{9}{2}}{5} \right) = -\frac{63}{256}. \end{align*}

  2. Proof. The proof is by induction. For n = 1 we have

        \[ a_1 = (-1)^1 \binom{-\frac{1}{2}}{1} = (-1) \left( -\frac{1}{2} \right) = \frac{1}{2} > 0. \]

    For n = 2 we have

        \[ a_2 = (-1)^2 \binom{-\frac{1}{2}}{2} = 1 \left( \frac{3}{8} \right) = \frac{3}{8}. \]

    Thus, for n = 1 we have

        \[ a_n > 0 \qquad \text{and} \qquad a_2 < a_1. \]

    Hence, the statement holds for the case n = 1. Assume then that the statement holds for n =k \in \mathbb{Z}_{\geq 1}. Then,

        \[ a_k > 0 \qquad \implies \qquad (-1)^k \binom{-\frac{1}{2}}{k} > 0. \]

    Furthermore, from the definition of a_n we have

        \begin{align*} a_{k+1} &= a_k \cdot (-1) \left( \frac{-\frac{1}{2} - k + 1}{k} \right) \\[9pt] &= a_k \cdot \left( \frac{ \frac{1}{2} + k - 1}{k} \right) \\[9pt] &= a_k \cdot \left( 1 - \frac{1}{2k} \right). \end{align*}

    But, 1 - \frac{1}{2k} > 0 for all positive integers k, and a_k > 0 by the induction hypothesis. Thus, a_{k+1} > 0. This gives us the first part of the statement, a_n> 0 for all positive integers n. Next, since

        \[ 0 < \left( 1 - \frac{1}{2k} \right) < 1 \]

    we have

        \[ a_k \cdot \left( 1 - \frac{1}{2k} \right) < a_k \quad \implies \quad a_{k+1} < a_k. \]

    Hence, both statements are true for all positive integers n. \qquad \blacksquare

Prove an identity of given finite sums

by RoRi

Prove the identity:

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

Proof. Using the hint (that \frac{1}{k+m+1} = \int_0^1 t^{k+m} \, dt) we start with the expression on the left,

    \begin{align*} \sum_{k=0}^n (-1)^k \binom{n}{k} \frac{1}{k+m+1} &= \sum_{k=0}^n (-1)^k \binom{n}{k} \int_0^1 t^{m+k} \, dt \\[10pt] &= \sum_{k=0}^n \int_0^1 (-1)^k \binom{n}{k} t^m t^k \, dt \\[10pt] &= \int_0^1 \sum_{k=0}^n (-1)^k \binom{n}{k} t^m t^k \, dt &(\text{finite sum}) \\[10pt] &= \int_0^1 t^m \sum_{k=0}^n \binom{n}{k} (-t)^k \, dt \\[10pt] &= \int_0^1 t^m \sum_{k=0}^n \binom{n}{k} (-t)^k (1)^{n-k} \, dt \\[10pt] &= \int_0^1 t^m (1-t)^n \, dt &(\text{Binomial theorem}). \end{align*}

(The interchange of the sum and integral is fine since it is a finite sum. Those planning to take analysis should note that this cannot always be done in the case of infinite sums.) Now, we have a reasonable integral, but we still want to get everything back into the form of the sum on the right so we make the substitution s = 1-t, ds = -dt. This gives us new limits of integration from 1 to 0. Therefore, we have

    \begin{align*} \sum_{k=0}^n (-1)^k \binom{n}{k} \frac{1}{k+m+1} &= \int_0^1 t^m (1-t)^n \, dt \\[10pt] &= -\int_1^0 (1-s)^m s^n \, ds \\[10pt] &= \int_0^1 (1-s)^m s^n \, ds \\[10pt] &= \int_0^1 s^n \sum_{k=0}^m \binom{m}{k} (-s)^k 1^{m-k} \, ds &(\text{Binomial theorem})\\[10pt] &= \int_0^1 \sum_{k=0}^m \binom{m}{k} (-1)^k s^{k+n} \, ds \\[10pt] &= \sum_{k=0}^m (-1)^k \binom{m}{k} \int_0^1 s^{k+n} \, ds \\[10pt] &= \sum_{k=0}^m (-1)^k \binom{m}{k} \frac{1}{k+n+1}. \qquad \blacksquare \end{align*}

Prove Leibniz’s formula

by RoRi

If h(x) = f(x) g(x) is a product of functions prove that the derivatives of h(x) are given by the formula

    \[ h^{(n)} (x) = \sum_{k=0}^n \binom{n}{k} f^{(k)} (x) g^{(n-k)}(x), \]

where

    \[ \binom{n}{k} = \frac{n!}{k! (n-k)!} \]

is the binomial coefficient. (See the first four exercises of Section I.4.10 on page 44 of Apostol, and in particular see Exercise #4, in which we prove the binomial theorem.)

Proof. The proof is by induction. Letting h(x) = f(x) g(x) and n = 1 we use the product rule for derivatives

    \[ h'(x) = f(x)g'(x) + f'(x)g(x) = \sum_{k=0}^1 \binom{1}{k} f^{(k)}(x) g^{(1-k)}(x). \]

So, the formula is true for the case n = 1. Assume then that it is true for n = m \in \mathbb{Z}_{> 0}. Then we consider the (m+1)st derivative h^{(m+1)}(x):

    \begin{align*} h^{(m+1)}(x) &= \left( h^{(m)}(x) \right)' \\ &= \left( \sum_{k=0}^m \binom{m}{k} f^{(k)}(x) g^{(m-k)}(x) \right)' &(\text{Ind. Hyp.})\\ &= \sum_{k=0}^m \left( \binom{m}{k} f^{(k)}(x) g^{(m-k)}(x) \right)'. \end{align*}

Here, we use linearity of the derivative to differentiate term by term over this finite sum. This property was established in Theorem 4.1 (i) and the comments following the theorem on page 164 of Apostol. Continuing where we left off we apply the product rule,

    \begin{align*} &= \sum_{k=0}^m \left( \binom{m}{k} \left(f^{(k+1)}(x) g^{(m-k)}(x) + f^{(k)}(x) g^{(m-k+1)}(x) \right) \right) \\[9pt] &= \sum_{k=0}^m \binom{m}{k} f^{(k+1)}(x)g^{(m-k)}(x) + \sum_{k=0}^m \binom{m}{k} f^{(k)}(x) g^{(m-k+1)}(x) \\[9pt] &= \sum_{k=1}^{m+1} \binom{m}{k-1} f^{(k)} g^{(m-k+1)}(x) + \sum_{k=0}^m \binom{m}{k} f^{(k)}(x) g^{(m-k+1)}(x), \end{align*}

where we’ve reindexed the first sum to run from k = 1 to m + 1 instead of from k = 0 to m. Then, we pull out the k = m+1 term from the first sum and the k = 0 term from the second,

    \begin{align*} &= f^{(m+1)}(x) g(x) + \sum_{k=1}^m \binom{m}{k-1} f^{(k)}(x) g^{(m-k+1)}(x) + \sum_{k=1}^m \binom{m}{k} f^{(k)}(x) g^{(m-k+1)}(x) + f(x) g^{(m+1)}(x) \\ &= f^{(m+1)}(x) g(x) + f(x)g^{(m+1)}(x) + \sum_{k=1}^m \left( \binom{m}{k-1} + \binom{m}{k} \right) f^{(k)}(x) g^{(m-k+1)} (x). \end{align*}

Now, we recall the law of Pascal’s triangle (which we proved in a previous exercise) which establishes that

    \[ \binom{m}{k} + \binom{m}{k-1} = \binom{m+1}{k}. \]

Therefore, we have

    \begin{align*} &= f^{(m+1)}(x) g(x) + f(x) g^{(m+1)}(x) + \sum_{k=1}^m \binom{m+1}{k} f^{(k)}(x)g^{(m-k+1)}(x) \\ &= \sum_{k=0}^{m+1} \binom{m+1}{k} f^{(k)}(x) g^{(m-k+1)}(x). \end{align*}

Hence, the formula holds for m+1 if it holds m. Therefore, we have established that it holds for all positive integers n.