Binomial Coefficient Stuff

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

Binomial Coefficient Stuff

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.

1270 posts

#1 h Mar 18, 2021, 4:48 AM

Y by

For positive integers $n \geq k,$ show that
$\frac{\binom{n+1}{k+1} \cdot \binom{n}{k}}{n-k+1}$ is an integer.
Idk, this problem feels easy, but I'm not getting anywhere so far.

Z K Y

The post below has been deleted. Click to close.

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

SilverDragon246

678 posts

SilverDragon246

#2 h Mar 18, 2021, 5:41 AM

Y by

Easiest is to just expand and try to show its an integer, alternatively, there seems like there is probably a combinatorial interpretation of this

Z K Y

The post below has been deleted. Click to close.

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

7554 posts

#3 h Mar 18, 2021, 5:48 AM • 2 Y

Y by aie8920, fungarwai

$\frac{\binom{n}{k}}{n-k+1} = \frac{n!}{(n-k+1)!k!} = \frac{1}{n+1}\binom{n+1}{k}$ so the problem reduces to showing $\binom{n+1}{k} \binom{n+1}{k+1}$ is divisible by $n+1$ for all $n \ge k$ . I'd imagine this is a well-known result or has an easier combinatorial interpretation...

Z K Y

The post below has been deleted. Click to close.

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

Billybillybobjoejr.

352 posts

Billybillybobjoejr.

#4 h Mar 18, 2021, 6:01 AM • 3 Y

Y by Mango247, Mango247, Mango247

i think there should be a nice proof using p-adic valuation on the prime factors of n+1 while using the property that gcd(k, k+1) = 1

Z K Y

The post below has been deleted. Click to close.

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

865 posts

#5 h Mar 20, 2021, 11:47 AM • 1 Y

Y by aie8920

$\nu_p((n+1)!n!)\ge \nu_p((k+1)!(n-k)!k!(n+1-k)!)$ caused by $(k,k+1)=1$

I prefer noting $n \mid \binom{n}{m}\binom{n}{m+1}$ on my blog as #3 suggested

Proof

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a