Please how is the combination addition formula ${{t}\choose{r}}={{t-1}\choose{r}}+{{t-1}\choose{r-1}}$ useful in proving the difference equation $\Delta_{t}{{r+t}\choose{t}}={{r+t}\choose{t+1}}$?

Secondly, does ${{t}\choose{k}}={{t}\choose{t-k}}$ need verification? I thought definition only testifies this.


The difference equation is an immediate consequence of the addition formula:




Whether the identity $\binom{t}k=\binom{t}{t-k}$ needs proof depends on how you defined the binomial coefficient. If you defined it in terms of factorials, virtually no proof is required. If you defined it combinatorially, or as

$$\binom{t}k=\frac{t^{\underline k}}{k!}\;,$$

then some argument is required.

  • $\begingroup$ Thanks so much Brian M. Scott. $\endgroup$
    – YYG
    Nov 13 '13 at 22:27
  • $\begingroup$ @YYG: You’re very welcome. $\endgroup$ Nov 13 '13 at 22:27
  • $\begingroup$ But Brian what is that argument that you have mentioned about because I consider the binomial coefficient in terms of the falling factorial like you have written there. $\endgroup$
    – YYG
    Nov 13 '13 at 22:30
  • $\begingroup$ @YYG: That identity is valid only for integer $t\ge 0$ and integer $k$, so I would simply show that if $0\le k\le t$, then $$\frac{t^{\underline k}}{k!}=\frac{t!}{k!(t-k)!}=\frac{t^{\underline{t-k}}}{(t-k)!}\;,$$ and if $k$ is an integer outside that range, then both binomial coefficients are $0$. $\endgroup$ Nov 13 '13 at 22:33
  • $\begingroup$ Okay, but sorry, how do you manage to 'kill' that $k!$ and get $t$ to the falling $t-k$ at the numerator on the last part? And by the way, the equation can be defined even for non-integer and/or negative values of $t$ if we utilize the definition of Gamma function. $\endgroup$
    – YYG
    Nov 13 '13 at 22:41

Just write your difference equation explicitely: $$\Delta_t \binom{r+t}{t}=\binom{r+t+1}{t+1}-\binom{r+t}{t} = \binom{r+t}{t+1}.$$

The identity $\binom{x}{y}=\binom{x}{x-y}$ is obvious if you defined binomial coefficients via factorials. If you have a combinatoric definition, then it's an evident exercise.

  • $\begingroup$ Thanks so much TZakrevskiy. $\endgroup$
    – YYG
    Nov 13 '13 at 22:26
  • $\begingroup$ @YYG you're welcome! $\endgroup$ Nov 13 '13 at 22:28

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.