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$.

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$

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.

it's a simple problem. haha

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 ?

$=\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!