4
$\begingroup$

I understand the relationship between Pascal's triangle and binomial expansion for nonnegative integer powers by using combination e.g the binomial coefficient for $x^3$ in $(a + x)^8$ is equivalent to how many ways there are to choose 3 $x$'s from 8 possibilities.

I thought this idea would fail with regards to negative binomial expansion but I find out we can have cases where $r<0$ in $nCr$.

Can someone intuitively explain this? I kind of understand binomial expansion using Maclaurin series but I can't wrap my head around what negative combination is intuitively and why it works for negative binomial expansion.

Basically I don't understand the reason behind the combination formula still working for negative numbers.

$\endgroup$
4
  • $\begingroup$ In the definition that I find most useful, $r$ is a non-negartive integer, but $n$ can take any real value. $\binom{n}{r}=\frac{n(n-1)(n-2)\cdots(n-r+1)}{r!}$. There are other definitions using the Ganma function for non-integer values of $r$, but they don't obey as many of the same relationships that the binomial coefficients with positive integral values do. $\endgroup$ – robjohn Feb 1 at 23:21
  • $\begingroup$ The generalized binomial series naturally implies the properties of the generalized binomial coefficient. $\endgroup$ – William Feb 6 at 20:59
  • $\begingroup$ You mean ${}_nC_r$ can have $n<0$, not $r<0$. $\endgroup$ – runway44 Mar 31 at 5:59
  • $\begingroup$ @runway44: Yes. $n$ can take any real value, but $r$ is a non-negative integer. $_nC_r=\binom{n}{r}$ is the coefficient of $x^r$ in the Taylor series for $(1+x)^n$. $\endgroup$ – robjohn Apr 1 at 18:59
1
$\begingroup$

The binomial identity \begin{align*} \color{blue}{\binom{n+1}{k+1}=\binom{n}{k+1}+\binom{n}{k}}\tag{1} \end{align*} is not only valid for natural numbers $n$ but also for $n\in\mathbb{Z}$ and $k\geq 0$ a natural number. We can use this relationship to extend the Pascal triangle to negative numbers $n$ shown in the table below. The numbers of the Pascal triangle for $n,k\geq 0$ follow by setting $\binom{n}{0}=1, \binom{0}{k}=\delta_{k,0}$. The entries with negative $n$ follow by extending the rule $\binom{n}{0}=1$ for $n\in\mathbb{Z}$. \begin{align*} \begin{array}{r|rrrrrrrrl} k&0&1&2&3&4&5&6&&\\ \hline n&\color{white}{-0}&\color{white}{-0}&\color{white}{-0}&\color{white}{-0}&\color{white}{-0}&\color{white}{-0}&\color{white}{-0}&&\\ -4&1&\color{blue}{-4}&\color{blue}{10}&-20&35&-56&84&&(1+x)^{-4}\\ -3&1&-3&\color{blue}{6}&-10&15&-21&28&&(1+x)^{-3}\\ -2&1&-2&3&-4&5&-6&7&&(1+x)^{-2}\\ -1&1&-1&1&-1&1&-1&1&&(1+x)^{-1}\\ 0&1&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&&(1+x)^0\\ 1&1&1&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&&(1+x)^1\\ 2&1&2&1&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&&(1+x)^2\\ 3&1&\color{blue}{3}&\color{blue}{3}&1&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&&(1+x)^3\\ 4&1&4&\color{blue}{6}&4&1&\color{lightgrey}{0}&\color{lightgrey}{0}&&(1+x)^4\\ \end{array} \end{align*}

When looking for instance at the last line of the table above we see the number $6$ is according to (1) the sum of the entry $3$ above $6$ with its left neighbor $3$. \begin{align*} 6=3+3\qquad\qquad \binom{4}{2}=\binom{3}{1}+\binom{3}{2} \end{align*} The algebraic connection is given by \begin{align*} \color{blue}{(1+x)^4=(1+x)(1+x)^3} \end{align*} or more detailed with $[x^k]$ denoting the coefficient of $x^k$: \begin{align*} \binom{4}{2}&=[x^2](1+x)^4\\ &=[x^2](1+x)(1+x)^3\\ &=\left([x^2]+[x^1]\right)(1+x)^3\\ &=\binom{3}{2}+\binom{3}{1}\tag{2} \end{align*} The algebraic connection holds also for negative $n$, for instance: \begin{align*} \color{blue}{(1+x)^{-3}=(1+x)(1+x)^{-4}} \end{align*} and we obtain similarly to (2): \begin{align*} 6=10+\left(-4\right)\qquad\qquad \binom{-3}{2}=\binom{-4}{2}+\binom{-4}{1} \end{align*} or more detailed with $[x^k]$ denoting the coefficient of $x^k$: \begin{align*} \binom{-3}{2}&=[x^2](1+x)^{-3}\\ &=[x^2](1+x)(1+x)^{-4}\\ &=\left([x^2]+[x^1]\right)(1+x)^{-4}\\ &=\binom{-4}{2}+\binom{-4}{1}\tag{2} \end{align*}

We can also see in the table the binomial identity \begin{align*} \binom{-n}{k}=\binom{n+k-1}{k}(-1)^k \end{align*} is given as rotation of a somewhat modified Pascal triangle. \begin{align*} \begin{array}{r|rrrrrrrrl} k&0&1&2&3&4&5&6&&\\ \hline n&\color{white}{-0}&\color{white}{-0}&\color{white}{-0}&\color{white}{-0}&\color{white}{-0}&\color{white}{-0}&\color{white}{-0}&&\\ -4&\color{blue}{1}&-4&10&-20&35&-56&84&&(1+x)^{-4}\\ -3&\color{blue}{1}&\color{blue}{-3}&6&-10&15&-21&28&&(1+x)^{-3}\\ -2&\color{blue}{1}&\color{blue}{-2}&\color{blue}{3}&-4&5&-6&7&&(1+x)^{-2}\\ -1&\color{blue}{1}&\color{blue}{-1}&\color{blue}{1}&\color{blue}{-1}&1&-1&1&&(1+x)^{-1}\\ 0&1&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&&(1+x)^0\\ 1&1&1&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&&(1+x)^1\\ 2&1&2&1&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&&(1+x)^2\\ 3&1&3&3&1&\color{lightgrey}{0}&\color{lightgrey}{0}&\color{lightgrey}{0}&&(1+x)^3\\ 4&1&4&6&4&1&\color{lightgrey}{0}&\color{lightgrey}{0}&&(1+x)^4\\ \end{array} \end{align*}

$\endgroup$
1
$\begingroup$

The Question

In this answer, it is shown that $$ \binom{-n}{j}=(-1)^j\binom{n+j-1}{j}\tag1 $$ If I understand correctly, the question is asking why, when $(1)$ is applied to the Binomial Theorem, we get $(1+x)^{-n}$.

Prior Results

In this answer are three proofs of this cancellation formula $$ \sum_{j=k}^n(-1)^{j-k}\binom{n}{j}\binom{j}{k} =[n=k]\tag2 $$ where $[\cdots]$ are Iverson Brackets.


Verification of $\bf{(1)}$ Using the Cauchy Product Formula

For $k\ge1$, we have $$ \begin{align} \sum_{j=0}^k\binom{-n}{j}\binom{n}{k-j} &=\sum_{j=0}^k(-1)^j\binom{n+j-1}{n-1}\binom{n}{n+j-k}\tag{3a}\\ &=\sum_{j=0}^k(-1)^j\sum_{i=0}^{k-1}\binom{n+j-k}{i}\binom{k-1}{n-1-i}\binom{n}{n+j-k}\tag{3b}\\ &=\sum_{i=0}^{k-1}(-1)^{n-k-i}\binom{k-1}{n-1-i}[n=i]\tag{3c}\\[9pt] &=0\tag{3d} \end{align} $$ Explanation:
$\text{(3a)}$: apply $(1)$ and the symmetry of Pascal's Triangle
$\text{(3b)}$: Vandermonde's Identity
$\text{(3c)}$: apply $(2)$
$\text{(3d)}$: $\binom{k-1}{-1}=0$

If $k=0$, the sum is $\binom{-n}{0}\binom{n}{0}=1$. Therefore, using $(1)$, $(2)$, and Vandermonde, we have shown $$ \sum_{j=0}^k\binom{-n}{j}\binom{n}{k-j}=[k=0]\tag4 $$ which by the Cauchy Product Formula verifies that $$ \underbrace{\sum_{j=0}^\infty\binom{-n}{j}x^j}_{(1+x)^{-n}}\ \underbrace{\sum_{j=0}^n\binom{n}{j}x^j}_{(1+x)^n}=1\tag5 $$


Verification of $\bf{(1)}$ Using Induction

Using the formula for the sum of a geometric series, we have $$ (1+x)^{-1}=\sum_{k=0}^\infty(-1)^kx^k\tag6 $$ We can verify $(1)$ inductively using $(6)$ and the Cauchy Product Formula. Assume that $(1)$ is true for a given $n$, then $$ \begin{align} (1+x)^{-n-1} &=\color{#C00}{(1+x)^{-1}}\color{#090}{(1+x)^{-n}}\tag{7a}\\[9pt] &=\sum_{k=0}^\infty\sum_{j=0}^k\color{#C00}{(-1)^{k-j}x^{k-j}}\color{#090}{(-1)^j\binom{n+j-1}{j}x^j}\tag{7b}\\ &=\sum_{k=0}^\infty\sum_{j=0}^k(-1)^k\binom{n+j-1}{j}x^k\tag{7c}\\ &=\sum_{k=0}^\infty(-1)^k\binom{n+k}{k}x^k\tag{7d}\\ \end{align} $$ Explanation:
$\text{(7b)}$: $(6)$ and the inductive hypothesis
$\text{(7c)}$: collect terms
$\text{(7d)}$: Hockey-Stick Identity

which verifies $(1)$ for $n+1$.

$\endgroup$
0
$\begingroup$

$(1+x)^{-n}$ can also be written as $\frac{1}{(1+x)^n}$.

The denominator can be expanded and then viewed as the usual identity $$\frac1{1-x}=1+x+x^2+\dots$$

For example with $n=2$:

$$1+(-2x-x^2)+(2x+x^2)^2+(-2x-x^2)^3+\dots$$

This can have the like terms collected, which gives:

$$\binom{-2}{1}=-2$$ $$\binom{-2}{2}=3$$

etc...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.