Another binomial coefficients sum

Art of Problem Solving

AoPS Online

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Another binomial coefficients sum

G H J

Reveal topic tags

binomial coefficients

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5 posts

#1 h Mar 3, 2022, 6:55 AM • 1 Y

Y by HWenslawski

Prove that $\sum_{k=0}^{n}{{\left(-1\right)}^{k}\binom{n}{k} \binom{2n-k}{n-k}} = 1$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

10631 posts

#2 h Mar 3, 2022, 4:12 PM • 2 Y

Y by HWenslawski, fungarwai

The sum equals $\sum_0^n (-1)^k {n\choose k} p(x-k)$ where $p(x):={x\choose n}$ and $x=2n$ . This sum equals $D^n p(x)$ where $D$ is the difference operator. Since $p$ has degree $n$ it is well-known that $D^np(x)=n! a$ where $a$ is the leading cft of $p$ . Since $a=1/n!$ , the sum equals 1, as stated.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1640 posts

#3 h Mar 3, 2022, 4:17 PM

Y by

alexheinis wrote:

The sum equals $\sum_0^n (-1)^k {n\choose k} p(x-k)$ where $p(x):={x\choose n}$ and $x=2n$ . This sum equals $D^n p(x)$ where $D$ is the difference operator. Since $p$ has degree $n$ it is well-known that $D^np(x)=n! a$ where $a$ is the leading cft of $p$ . Since $a=1/n!$ , the sum equals 1, as stated.

I just saw lots of new notations without actual prove process.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

10631 posts

#6 h Mar 3, 2022, 4:37 PM • 1 Y

Y by fungarwai

@above: it's not my fault that you don't know the theory, since it is well-known and basic.
The notations might be new to you but they are standard. So you're wrong when you say that there is no actual proof.
Let $p$ be a polynomial. The difference polynomial $Dp$ is defined with $Dp(x)=p(x)-p(x-1)$ .
With induction one shows $D^n(p)(x)=\sum_{k=0}^n (-1)^k {n\choose k} p(x-k)$ .
If $\deg(p)=s$ then $\deg(Dp)=s-1$ and the leading cft is multiplied by a factor $s$ .
In particular, if $\deg (p)=n$ then $D^n (p)$ is a constant polynomial, and it's value is $n! a$ , where $a$ is the leading cft of $p$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1640 posts

#7 h Mar 3, 2022, 5:01 PM

Y by

@above,
A well proof should be a friendly one, no matter it is well-known or new to the reader.
Anyway, thanks for explanation.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

588 posts

#8 h Mar 4, 2022, 5:50 AM • 1 Y

Y by fungarwai

Consider functions
$F(x) = \sum_{k\ge0} (-1)^k\binom{n}{k} x^k = (1-x)^n$
and the well-known $G_m(x) = \sum_{k\ge0} \binom{m+k}{k}x^k = \frac{1}{(1-x)^{m+1}}$
Then $F(x)G_m(x) = \sum_{n\ge0} \sum_{k=0}^n (-1)^k\binom{n}{k} \binom{m+n-k}{n-k} x^n = \frac{(1-x)^n}{(1-x)^{m+1}}$ Equating the coefficients of $x^n$ gives
$\begin{align*} [x^n] F(x)G_n(x) &= [x^n] \frac{1}{1-x}\\ \implies \sum_{k=0}^n (-1)^k\binom{n}{k} \binom{2n-k}{n-k} &= 1 \end{align*}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

226 posts

#9 h Apr 27, 2025, 5:27 AM • 1 Y

Y by soryn

Cute

This post has been edited 6 times. Last edited by P162008, Apr 28, 2025, 3:21 PM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

865 posts

#10 h Apr 27, 2025, 7:21 AM • 3 Y

Y by Taiharward, soryn, P162008

This is a special case of the formula $\boxed{\displaystyle \sum_{i=0}^k (-1)^{k-i}\binom ni \binom {m-1+k-i}{k-i}=\binom {n-m}k}$ introduced in Summation with binomial coefficient

The proof is similar to #8 in this post.

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

$\displaystyle \sum_{k=0}^n (-1)^{k}\binom nk \binom {2n-k}{n-k}=(-1)^n\binom {-1}n=1$

Applying difference operator as #2 is also a clever thought in this case.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5348 posts

soryn

#11 h Apr 27, 2025, 4:49 PM

Y by

Very, very nice!

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a