Home » Binomial Theorem

Tag: Binomial Theorem

Find the Taylor polynomial of (1 + x)α

by RoRi

Show that

    \[ T_n ((1+x)^{\alpha}) = \sum_{k=0}^n \binom{\alpha}{k} x^k, \]

where

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

Since we do not have the binomial theorem for real powers (we have proved a formula for (a+b)^n for integers n, but in this case the power we have is a real number \alpha), we use induction to determine the kth derivative of the function f(x) = (1+x)^{\alpha}. First, we compute a few derivatives of f(x),

    \begin{align*} f'(x) &= \alpha (1+x)^{\alpha - 1} \\ f''(x) &= \alpha(\alpha - 1)(1+x)^{\alpha - 2} \\ f'''(x) &= \alpha (\alpha - 1)(\alpha - 2) (1+x)^{\alpha - 3}. \end{align*}

So, we conjecture

    \[ f^{(n)} (x) = n! \cdot \binom{\alpha}{n} (1+x)^{\alpha - n}.\]

We have shown this is true for n =1, and if we suppose it is true for a positive integer k then we have

    \begin{align*} f^{(k+1)}(x) = (f^{(k)}(x))' &= \left( k! \binom{\alpha}{k} (1+x)^{\alpha -k} \right)' \\[9pt] &= k! \binom{\alpha}{k} (\alpha - k) (1+x)^{\alpha - (k+1)} \\[9pt] &= (k+1)! \binom{\alpha}{k+1} (1+x)^{\alpha - (k+1)}. \end{align*}

Therefore, the formula holds for all positive integers. Now we can compute the Taylor polynomial directly,

    \begin{align*} T_n (1+x)^{\alpha} &= \sum_{k=0}^n \frac{f^{(k)}(0)}{k!} x^k \\[9pt] &= \sum_{k=0}^n \binom{\alpha}{k} x^k. \end{align*}

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.

Fundamental properties of polynomials

by RoRi

Consider a polynomial of degree n,

    \[ f(x) = \sum_{k=0}^n c_k x^k = c_0 + c_1 x + \cdots + c_n x^n. \]

  1. Prove that if f(0) = 0 and n \geq 1 then there is an n-1 degree polynomial g(x) such that f(x) = x g(x).
  2. Prove that p(x) = f(x+a) is a polynomial of degree n for any a \in \mathbb{R}.
  3. Prove that if n \geq 1 and f(a) = 0, then f(x) = (x-a)h(x), for a polynomial h(x) of degree n-1.
  4. If f(x) has n+1 real zeros (i.e., there exist n+1 numbers x \in \mathbb{R} such that f(x) = 0), then c_k =0 for all k = 0, \ldots, n, and f(x) = 0 for all x \in \mathbb{R}.
  5. If

        \[ g(x) = \sum_{k=0}^m b_k x^k \]

    is a polynomial of degree m \geq n, and if

        \[ g(x) = f(x) \]

    for m+1 distinct x \in \mathbb{R}, then

        \[ m=n, \qquad b_k = c_k \quad \text{for each } k, \qquad g(x) = f(x) \quad \text{for all } x \in \mathbb{R}. \]

  1. Proof. First,

        \[ f(0) = 0 \quad \implies \quad c_0 + c_1 \cdot 0 + \cdots + c_{n-1} \cdot 0^{n-1} + c_n 0^n = 0 \quad \implies \quad c_0 = 0. \]

    Thus,

        \begin{align*} f(x) &= c_1x + c_2 x^2 + \cdots + c_n x^n \\ &= x (c_1 + c_2 x + \cdots + c_n x^{n-1}) \\ &= x g(x) \end{align*}

    where g(x) = \sum_{k=0}^{n-1} c_{k+1} x^k is then an n-1 degree polynomial. \qquad \blacksquare

  2. Proof. We compute, using the binomial theorem,

        \begin{align*} p(x) = f(x+a) &= \sum_{k=0}^n (x+a)^k c_k \\ &= c_0 + (x+a)c_1 + (x+a)^2 c_2 + \cdots + (x+a)^n c_n \\ &= c_0 + c_1 \left(\sum_{j=0}^1 \binom{1}{j} a^j x^{1-j}\right) + c_2 \left( \sum_{j=0}^2 \binom{2}{j} a^j x^{2-j} \right) + \cdots + c_n \left( \sum_{j=0}^n \binom{n}{j} a^j x^{n-j} \right) \end{align*}

    Now, we want to group together the coefficients on the like-powers of x. So we pull out the terms corresponding to x^0, x^1, etc. This gives us,

        \begin{align*} &= (c_0 + ac_1 + a^2 c_2 + \cdots + a^n c_n) + x(c_1 + 2ac_2 + \cdots + na^{n-1}c_n) \\ &\qquad \qquad + x^2\left(c_2 + 3ac_3 + \cdots + \binom{n}{n-2}a^{n-2} c_n \right) + \cdots + x^n c_n \\ &= \sum_{k=0}^n \left( x^k \left( \sum_{j=k}^n \binom{j}{j-k} c_j a^{j-k} \right) \right). \end{align*}

    In the final line, we rewrote the coefficients as sums to view them a little more concisely. Either way, since a and all of the c_i‘s are constants, we have \sum_{j=k}^n \binom{j}{j-k} c_j a^{j-k} is some constant for each k, say d_k and we have,

        \[ p(x) = \sum_{k=0}^n d_k x^k. \]

    Hence, p(x) is a polynomial of degree n. \qquad \blacksquare

  3. Proof. From part (b) we know that if f(x) is a polynomial of degree n, then p(x) = f(x+a) is also a polynomial of the same degree. Further,

        \[ f(a) = 0 \quad \implies \quad p(0) = f(a) = 0. \]

    So, by part (a), we have

        \[ p(x) = x \cdot g(x) \]

    where g(x) is a polynomial of degree n-1. Thus,

        \[ p(x-a) = f(x) = (x-a)\cdot g(x-a). \]

    But, if g(x) is a polynomial of degree n-1, then by part (b) again, so is h(x) = g(x+(-a))= g(x-a). Hence,

        \[ f(x) = (x-a) \cdot h(x) \]

    for h a degree n-1 polynomial, as requested. \qquad \blacksquare

  4. Proof. The proof is by induction. First, we consider the case in which n = 1. Then f(x) = c_0 + c_1 x. Since the assumption is that there are n+1 distinct real x such that f(x) = 0, we know there exist a_1, a_2 \in \mathbb{R} such that

        \[ f(a_1) = f(a_2) = 0, \qquad a_1 \neq a_2. \]

    Thus,

        \begin{align*} c_0 + c_1 a_1 = c_0 + c_1 a_2 = 0 && \implies && c_1 a_1 - c_1 a_2 &= 0 \\ && \implies && c_1 (a_1 - a_2) &= 0 \\ && \implies && c_1 &= 0 & (\text{since } a_1 \neq a_2)\\ && \implies && c_0 &= 0 & (\text{since } c_0 + c_1 a_1 = 0). \end{align*}

    Hence, the statement is true for n=1. Assume that it is true for some n = k \in \mathbb{Z}_{>0}. Then, let f(x) be a polynomial of degree k+1 with k+2 distinct real zeros, a_1, \ldots, a_{k+2}. Then, since f(a_{k+2}) = 0, using part (c), we have,

        \[ f(x) = (x - a_{k+2})h(x) \]

    where h(x) is a polynomial of degree k. Further, we know there are k+1 distinct values a_1, \ldots, a_{k+1} such that h(a_i) = 0. (Since f(a_i) = 0 for 1 \leq i \leq k+2 and (x - a_{k+2}) \neq 0 for x = a_i with 1 \leq i \leq k+1 since all of the a_i are distinct.) Thus, by the induction hypothesis, every coefficient of h is 0 and h(x) = 0 for all x \in \mathbb{R}. Thus,

        \begin{align*} f(x) = (x - a_{k+2}) h(x) &= (x-a_{k+2}) \cdot \sum_{j=0}^k c_j x^j \\ &= \sum_{j=0}^k (x-a_{k+2})c_j x^j \\ &= c_k x^{k+1} + (c_{k-1} - a_{k+2} c_k)x^k + \cdots + (c_1 - a_{k+2} c_0) x + a_{k+2} c_0. \end{align*}

    But, since all of the coefficients of h(x) are zero, we have c_i = 0 for i = 1, \ldots k. Hence,

        \[ f(x) = 0 \cdot x^{k+1} + 0 \cdot x^k + \cdots + 0 \cdot x + 0 = 0 \qquad \text{for all } x \in \mathbb{R}. \]

    Thus, all of the coefficients of f are zero and f(x) = 0 for all x \in \mathbb{R}. Hence, the statement is true for the case k+1, and therefore, for all n \in \mathbb{Z}_{>0}. \qquad \blacksquare

  5. Proof. Let

        \[ p(x) = g(x) - f(x) = \sum_{k=0}^m b_k x^k - \sum_{k=0}^n c_k x^k = \sum_{k=0}^m (b_k - c_k)x^k \]

    where c_k = 0 for n < k \leq m (we have m \geq n by assumption).
    Then, there are m+1 distinct real x for which p(x) = 0. (Since there are m+1 distinct real values for which g(x) = f(x), and so at each of these values p(x) = g(x) - f(x) = 0.) Thus, by part (d), b_k - c_k = 0 for k = 0, \ldots, m and p(x) = 0 for all x \in \mathbb{R}. But then,

        \[ b_k - c_k = 0 \quad \implies \quad b_k = c_k \qquad \text{for }k =0, \ldots, m \]

    and

        \[ p(x) = 0 \quad \implies \quad g(x) - f(x) = 0 \quad \implies \quad f(x) = g(x), \]

    for all x \in \mathbb{R}. Further, since b_k - c_k = 0 for k = 0, \ldots, m, and by assumption c_k = 0 for k = n+1, \ldots, m, we have b_k = 0 for k = n+1, \ldots, m. But then,

        \[ g(x) = \sum_{k=0}^n b_k x^k + \sum_{k=n+1}^m 0 \cdot x^k = \sum_{k=0}^n b_k x^k \]

    means g(x) is a polynomial of degree n as well. \qquad \blacksquare

Prove a formula for b^p – a^p and a resulting inequality

by RoRi
  1. Prove that for any p \in \mathbb{Z}_{>0} we have

        \[ b^p - a^p = (b-a)(b^{p-1} + b^{p-2}a + b^{p-3} a^2 + \cdots + ba^{p-2} + a^{p-1}). \]

  2. For p \in \mathbb{Z}_{>0} and n \in \mathbb{Z}_{>0} prove that

        \[ n^p < \frac{(n+1)^{p+1} - n^{p+1}}{p+1} < (n+1)^p. \]

  3. Again for n,p \in \mathbb{Z}_{>0} prove

        \[ \sum_{k=1}^{n-1} k^p < \frac{n^{p+1}}{p+1} < \sum_{k=1}^n k^p. \]

  1. Proof. First we rewrite the sum on the right in summation notation, and then use the distributive property to compute,

        \begin{align*} (b-a) (b^{p-1} + b^{p-2}a + \cdots + &ba^{p-2} + a^{p-1}) \\ &= (b-a)\left(\sum_{k=0}^{p-1} b^{p-k-1} a^k \right) \\ &= b \left( \sum_{k=0}^{p-1} b^{p-k-1} a^k \right) - a \left( \sum_{k=0}^{p-1} b^{p-k-1}a^k \right) \\ &= \sum_{k=0}^{p-1} b^{p-k} a^k - \sum_{k=0}^{p-1} b^{p-k} a^{k+1} \\ &= \sum_{k=0}^{p-1} b^{p-k} a^k - \sum_{k=1}^p b^{p-k} a^k & (\text{reindexing 2nd sum})\\ &= b^p + \sum_{k=1}^{p-1} b^{p-k} a^k - \left(\left(\sum_{k=1}^{p-1} b^{p-k} a^k\right) + a^p \right) \\ &= b^p - a^p & (\text{sums cancel}). \end{align*}

    This is the identity requested. \qquad \blacksquare

  2. Proof. From the Binomial theorem we have

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

    Thus,

        \begin{align*} \frac{(n+1)^{p+1} - n^{p+1}}{p+1} &= \left(\frac{1}{p+1}\right) \left( \left(\sum_{k=0}^{p+1} \binom{p+1}{k}n^k \right) - n^{p+1} \right)\\ &= \left( \frac{1}{p+1} \right) \left(n^{p+1} + (p+1)n^p + \left( \sum_{k=2}^{p+1} \binom{p+1}{k} n^k \right) - n^{p+1}\right)\\ &= n^p + \left(\frac{1}{p+1} \right) \left( \sum_{k=2}^{p+1} \binom{p+1}{k} n^k \right)\\ &> n^p \end{align*}

    since the second term is strictly positive for n,p positive integers. This establishes the inequality on the left.
    For the inequality on the right we use part (a) to get,

        \[ (n+1)^{p+1} - n^{p+1} = (n+1-n) \cdot ((n+1)^p + n(n+1)^{p-1} + \cdots + n^{p-1} (n+1) + n^p ). \]

    Thus,

        \begin{align*} \frac{(n+1)^{p+1} - n^{p+1}}{p+1} &= \left( \frac{1}{p+1} \right) \left((n+1)^p + n(n+1)^{p-1} + \cdots + n^{p-1}(n+1) + n^p\right) \\ &< \left( \frac{1}{p+1} \right) ((n+1)^{p+1} + (n+1)^p + \cdots + (n+1)^p) \\ &= \left( \frac{1}{p+1} \right) ((p+1)(n+1)^p) \\ & = (n+1)^p. \end{align*}

    In the second to last line we have just replaced each term n in the sum by n+1, giving the inequality. This establishes both sides of the requested inequality. \qquad \blacksquare

  3. Proof. The proof is by induction. For the case n= 1 we have,

        \[ \sum_{k=1}^{n-1} k^p = \sum_{k=1}^0 k^p =0, \qquad \frac{n^{p+1}}{p+1} = \frac{1}{p+1}, \qquad \sum_{k=1}^n k^p = \sum_{k=1}^1 k^p = 1. \]

    For a positive integer p, then 0 < \frac{1}{p+1} < 1; hence, the inequalities hold in the case n =1. Assume then that they hold for some n = m \in \mathbb{Z}_{>0}.
    For the left inequality,

        \begin{align*} \sum_{k=1}^{m-1} k^p < \frac{m^{p+1}}{p+1} &&\implies \sum_{k=1}^m k^p &< \frac{m^{p+1}}{p+1} + m^p \\ &&&< \frac{m^{p+1} + (m+1)^{p+1} - m^{p+1}}{p+1} &(\text{part (b)})\\ &&&= \frac{(m+1)^{p+1}}{p+1}. \end{align*}

    This establishes the left inequality for all n \in \mathbb{Z}_{>0}.
    For the right inequality, assume it is true for some n = m \in \mathbb{Z}_{>0}, then

        \begin{align*} \frac{m^{p+1}}{p+1} < \sum_{k=1}^m k^p \ &\implies& \frac{m^{p+1}}{p+1} + (m+1)^p &< \sum_{k=1}^{m+1} k^p \\ &\implies& \frac{m^{p+1} + (m+1)^{p+1} - m^{p+1}}{p+1} &< \sum_{k=1}^{m+1} k^p & (\text{part (b)})\\ &\implies& \frac{(m+1)^{p+1}}{p+1} &< \sum_{k=1}^{m+1} k^p. \end{align*}

    Hence, the right inequality is true for all n \in \mathbb{Z}_{>0}. Therefore, the inequalities requested are indeed true for all n \in \mathbb{Z}_{>0}. \qquad \blacksquare

Prove some inequalities about (1+1/n)^n for positive integers n

by RoRi
  1. For n \in \mathbb{Z}_{>0} prove,

        \[ \left( 1 + \frac{1}{n} \right)^n = 1 + \sum_{k=1}^n \left( \frac{1}{k!} \cdot \prod_{r=0}^{k-1} \left(1 - \frac{r}{n}\right) \right). \]

  2. For n > 1, prove

        \[ 2 < \left( 1 + \frac{1}{n} \right)^n < 1 + \sum_{k=1}^n \frac{1}{k!} < 3. \]

  1. Proof. Recall the Binomial theorem,

        \[ (a+b)^n = \sum_{k=0}^n \binom{n}{k} \left( \frac{1}{n} \right)^k. \]

    So, letting a = \frac{1}{n} and b = 1 we have,

        \begin{align*} \left(1 + \frac{1}{n}\right)^n &= \sum_{k=0}^n \binom{n}{k} \left(\frac{1}{n} \right)^k \\ &= 1 + \sum_{k=1}^n \binom{n}{k} \left( \frac{1}{n} \right)^k \\ &= 1 + \sum_{k=1}^n \frac{n!}{k! (n-k)!} \left( \frac{1}{n} \right)^k &(\text{Def. of } \binom{n}{k})\\ &= 1 + \sum_{k=1}^n \frac{1}{k!} \left( \left( \frac{\prod_{r=1}^n r}{\prod_{r=1}^{n-k} r} \right) \cdot \left( \frac{1}{n} \right)^k \right) &(\text{Def. of } n!)\\ &= 1 + \sum_{k=1}^n \frac{1}{k!} \left(\prod_{r=n-k+1}^n r \right) \left( \frac{1}{n} \right)^k &(\text{cancelling})\\ &= 1 + \sum_{k=1}^n \frac{1}{k!} \left(\prod_{r=0}^{k-1} (n-r) \right) \left( \frac{1}{n} \right)^k &(\text{reindexing prod.})\\ &= 1 + \sum_{k=1}^n \frac{1}{k!} \left( \prod_{r=0}^{k-1} (n-r) \right) \left( \prod_{r=0}^{k-1} \frac{1}{n} \right) &(\text{rewritting } (1/n)^k \text{ as prod})\\ &= 1 + \sum_{k=1}^n \frac{1}{k!} \left( \prod_{r=0}^{k-1} \left( 1 - \frac{r}{n} \right) \right). \qquad \blacksquare \end{align*}

  2. Proof. First, we prove the left inequality,

        \[ 2 < \left( 1 + \frac{1}{n} \right)^n. \]

    If n > 1, then n \geq 2, so using the Binomial theorem we have,

        \[ \left( 1 + \frac{1}{n} \right)^n = \sum_{k=0}^n \binom{n}{k} \left( \frac{1}{n} \right)^k \ \implies \ \left( 1 + \frac{1}{n} \right)^n = 1 + n\left(\frac{1}{n} \right) + \sum_{k=2}^n \binom{n}{k} \left( \frac{1}{n} \right)^k > 2. \]

    Where we know the inequality is strict since there is at least one term (which is necessarily positive) in \sum_{k=2}^n \binom{n}{k} \left( \frac{1}{n} \right)^k since n \geq 2.
    Next, we prove the middle inequality,

        \[ \left( 1 + \frac{1}{n} \right)^n < 1 + \sum_{k=1}^n \frac{1}{k!}. \]

    By part (a) we know,

        \[ \left( 1+ \frac{1}{n} \right)^n = 1 + \sum_{k=1}^n \frac{1}{k!} \left( \prod_{r=0}^{k-1} \left( 1 - \frac{r}{n} \right) \right). \]

    Further, for n > 1 we have \left(1 - \frac{r}{n}\right) < 1 for all r = 0, \ldots, n-1. Thus, we know that,

        \[ \prod_{r=0}^{k-1} \left(1 - \frac{r}{n} \right) < \prod_{r=0}^{k-1} 1 = 1. \]

    Hence,

        \[ \frac{1}{k!} \left( \prod_{r=0}^{k-1} \left(1 - \frac{r}{n} \right) \right) < \frac{1}{k!} \]

    for all k. Therefore, we have established the second inequality,

        \[ \left(1 + \frac{1}{n} \right)^n = 1+ \sum_{k=1}^n \frac{1}{k!} \left( \prod_{r=0}^{k-1} \left( 1 - \frac{r}{n} \right) \right) < 1 + \sum_{k=1}^n \frac{1}{k!}. \]

    Finally, we prove the right inequality,

        \[ 1 + \sum_{k=1}^n \frac{1}{k!} < 3. \]

    Here we expand the first few terms and use a previous result,

        \begin{align*} 1 + \sum_{k=1}^n \frac{1}{k!} &= 1 + 1 + \frac{1}{2} + \frac{1}{6} + \sum_{k=4}^n \frac{1}{k!} \\ &< \frac{8}{3} + \sum_{k=4}^n \frac{1}{2^k} & (2^k < k! \implies \frac{1}{2^k} > \frac{1}{k!})\\ &= \frac{8}{3} + \frac{1}{16} \left( \sum_{k=0}^{n-4} \frac{1}{2^k} \right) & (\text{reindexing and pulling out } \frac{1}{2^4}) \\ &= \frac{8}{3} + \frac{1}{16} \left( 2 - \frac{1}{2^{n-4}}\right) \\ &= \frac{8}{3} + \frac{1}{8} - \frac{1}{2^n} \\ &< 3 \end{align*}

    for all n > 1. In the second to last line we used this result on the kth powers of a real number x (in this case x = \frac{1}{2}). This completes the proof for all of the inequalities requested. \qquad \blacksquare

Prove the binomial theorem by induction

by RoRi

Prove the binomial theorem:

    \[ (a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}. \]

Further, prove the formulas:

    \[ \sum_{k=0}^n \binom{n}{k} = 2^n \qquad \text{and} \qquad \sum_{k=0}^n (-1)^k \binom{n}{k}, \ \ \text{for } n > 0. \]

First, we prove the binomial theorem by induction.
Proof. For the case n =1 on the left we have,

    \[ (a+b)^n = (a+b)^1 = a+b. \]

On the right,

    \[ \sum_{k=0}^n \binom{n}{k} a^k b^{n-k} = \sum_{k=0}^1 \binom{n}{k} a^k b^{n-k} = \binom{1}{0} a^0 b^{1-0} + \binom{1}{1}a^1 b^{1-1} = b + a = a + b. \]

Hence, the formula is true for the case n=1.
Assume then that the formula is true for some n = m \in \mathbb{Z}_{>0}. Then we have,

    \begin{align*} &&(a+b)^m &= \sum_{k=0}^m \binom{m}{k} a^k b^{m-k} \\ &\implies & (a+b)^{m+1} &= \left(\sum_{k=0}^m \binom{m}{k} a^k b^{m-k} \right) (a+b) \\ &\implies & (a+b)^{m+1} &= \sum_{k=0}^m \binom{m}{k} a^{k+1} b^{m-k} + \sum_{k=0}^m \binom{m}{k} a^k b^{m+1-k}\\ &&&= a^{m+1} + \sum_{k=0}^{m-1} \binom{m}{k} a^{k+1} b^{m-k} + \sum_{k=0}^m \binom{m}{k} a^k b^{m+1-k} \\ &&&= a^{m+1} + \sum_{k=1}^m \binom{m}{k-1} a^{k} b^{m+1-k} + \sum_{k=0}^m \binom{m}{k} a^k b^{m+1-k} & (\text{reindex})\\ &&&= a^{m+1} + b^{m+1} + \sum_{k=1}^m \binom{m}{k-1} a^{k} b^{m+1-k} + \sum_{k=1}^m \binom{m}{k} a^k b^{m+1-k} \\ &&&= a^{m+1} + b^{m+1} + \sum_{k=1}^m \left( \left( \binom{m}{k-1} + \binom{m}{k} \right) (a^k b^{m+1-k}) \right) \\ &&&= a^{m+1} + b^{m+1} + \sum_{k=1}^m \binom{m+1}{k} a^k b^{m+1-k} & (\text{I.4.10, #3}) \\ &&&= \sum_{k=0}^{m+1} \binom{m+1}{k} a^k b^{m+1-k}. \end{align*}

Thus, if the formula is true for the case m then it is true for the case m+1. Hence, we have proved the formula for all n \in \mathbb{Z}_{>0}. \qquad \blacksquare

As an application of the binomial theorem we then prove the two formulas.
For the first, apply the binomial theorem with a = b = 1. Then,

    \[ (a+b)^n = \sum_{k=0}^n a^k b^{n-k} \quad \implies \quad (1+1)^n = 2^n = \sum_{k=0}^n \binom{n}{k}. \]

For the second, apply the binomial theorem with a=-1 and b =1. Then,

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