Mongolia TST 2011 Test 1 #2 Let p be a prime number. Prove that: \sum_{k=0}^p (-1)^k \dbinom{p}{k} \dbinom{p+k}{k} \equiv -1 (\mod p^3) (proposed by B. Batbayasgalan, inspired by Putnam olympiad problem) Note: I believe they meant to say p>2 as well.
Problem
Source: Mongolia TST 2011 Test 1 #2
Tags: Putnam, function, number theory unsolved, number theory
07.11.2011 08:09
Bacteria wrote: Mongolia TST 2011 Test 1 #2 Let p be a prime number. Prove that: \sum_{k=0}^p (-1)^k \dbinom{p}{k} \dbinom{p+k}{k} \equiv -1 (\mod p^3) (proposed by B. Batbayasgalan, inspired by Putnam olympiad problem) Note: I believe they meant to say p>2 as well. Very interesting! We have \sum_{k=0}^p (-1)^k \dbinom{p}{k} \dbinom{p+k}{k}=(-1)^p for all positive integers p.
08.11.2011 07:42
nnosipov wrote: We have \sum_{k=0}^p (-1)^k \dbinom{p}{k} \dbinom{p+k}{k}=(-1)^p for all positive integers p. I'll assume p is odd : \sum_{k=0}^{p}(-1)^{k}\dbinom{p}{k}\dbinom{p+k}{k} =\: [-x^p] \, \, \: (\sum_{k \ge 0}^{ }\binom{p+k}{k} x^k)( -\sum_{k=0}^{p} (-1)^{p-k} \binom{p}{p-k} x^k) =[-x^p] \, \, \: (\frac{1}{(1-x)^{p+1}}) . (1-x)^p=[x^p] \: \frac{-1}{1-x} = -1
09.11.2011 13:17
first note that \dbinom{n}{k} \dbinom{n+k}{k}=\dbinom{2k}{k} \dbinom{n+k}{2k}. now using generating functions we have: \sum_{n\ge 0} \sum_{k=0}^{n}(-1)^k \dbinom{n}{k} \dbinom{n+k}{k}x^n = \sum_{n\ge 0} \sum_{k=0}^{n}(-1)^k \dbinom{2k}{k} \dbinom{n+k}{2k}x^n =\sum_{k\ge 0} (-1)^k x^{-k} \dbinom{2k}{k} \sum_{n\ge 0} \dbinom{n+k}{2k} x^{n+k} =\sum_{k\ge 0} (-1)^kx^{-k}\dbinom{2k}{k} \frac{x^{2k}}{(1-x)^{2k+1}} =\frac{1}{1-x}\sum_{k\ge 0} \dbinom{2k}{k}(\frac{-x}{(1-x)^2})^k =\frac{1}{1-x}.\frac{1-x}{1+x}=\frac{1}{1+x}, so the coefficient of x^n is (-1)^n, as desired.
24.10.2013 07:17
it's a simple problem. haha
02.09.2019 19:30
mahanmath wrote: nnosipov wrote: We have \sum_{k=0}^p (-1)^k \dbinom{p}{k} \dbinom{p+k}{k}=(-1)^p for all positive integers p. I'll assume p is odd : \sum_{k=0}^{p}(-1)^{k}\dbinom{p}{k}\dbinom{p+k}{k} =\: [-x^p] \, \, \: (\sum_{k \ge 0}^{ }\binom{p+k}{k} x^k)( -\sum_{k=0}^{p} (-1)^{p-k} \binom{p}{p-k} x^k) =[-x^p] \, \, \: (\frac{1}{(1-x)^{p+1}}) . (1-x)^p=[x^p] \: \frac{-1}{1-x} = -1 can anyone explain, please ?
04.09.2019 13:47
=\frac{1}{1-x}.\frac{1-x}{1+x}=\frac{1}{1+x} Could you please explain to me how the 1-x/1+x comes?thanks!