Peter wrote: Suppose that $p$ is an odd prime. Prove that \[\sum_{j=0}^{p}\binom{p}{j}\binom{p+j}{j}\equiv 2^{p}+1\pmod{p^{2}}.\] For any integer $j$ with $1\leq j\leq p-1$, we have $\binom{p+j}{j}\cdot j!=\frac{\left(p+j\right)\cdot\left(\left(p+j\right)-1\right)\cdot ...\cdot\left(\left(p+j\right)-j+1\right)}{j!}\cdot j!$ $=\left(p+j\right)\cdot\left(\left(p+j\right)-1\right)\cdot ...\cdot\left(\left(p+j\right)-j+1\right)=\left(p+j\right)\cdot\left(p+j-1\right)\cdot ...\cdot\left(p+1\right)$ $\equiv j\cdot\left(j-1\right)\cdot ...\cdot 1=j!\text{ mod }p$, and since $j!$ is coprime to $p$ (since $j!=1\cdot 2\cdot ...\cdot j$, and each of the numbers $1$, $2$, ..., $j$ is coprime to $p$ because $p$ is prime and $j<p$), we can divide this congruence by $j!$ and obtain $\binom{p+j}{j}\equiv 1\text{ mod }p$, so that $p\mid \binom{p+j}{j}-1$. On the other hand, since $1\leq j\leq p-1$, we have $p\mid\binom{p}{j}$. Thus, $p\cdot p\mid\binom{p}{j}\cdot\left(\binom{p+j}{j}-1\right)$, what rewrites as $p^{2}\mid\binom{p}{j}\binom{p+j}{j}-\binom{p}{j}$. Hence, $\binom{p}{j}\binom{p+j}{j}\equiv\binom{p}{j}\text{ mod }p^{2}$. This has now been proven for $1\leq j\leq p-1$, but it is also true for $j=0$ (because $\binom{p}{0}\binom{p+0}{0}=1\cdot 1=1=\binom{p}{0}$). Thus, $\binom{p}{j}\binom{p+j}{j}\equiv\binom{p}{j}\text{ mod }p^{2}$ holds for every $j$ such that $0\leq j\leq p-1$. Thus, $\sum_{j=0}^{p}\binom{p}{j}\binom{p+j}{j}=\sum_{j=0}^{p-1}\binom{p}{j}\binom{p+j}{j}+\binom{p}{p}\binom{p+p}{p}\equiv\sum_{j=0}^{p-1}\binom{p}{j}+\binom{p}{p}\binom{p+p}{p}$ $=\left(\sum_{j=0}^{p}\binom{p}{j}-\binom{p}{p}\right)+1\binom{2p}{p}=\left(2^{p}-1\right)+\binom{2p}{p}\text{ mod }p^{2}$. Now, we will show that $\binom{2p}{p}\equiv 2\text{ mod }p^{2}$. Once this is shown, we can conclude that $\sum_{j=0}^{p}\binom{p}{j}\binom{p+j}{j}\equiv \left(2^{p}-1\right)+\binom{2p}{p}\equiv\left(2^{p}-1\right)+2=2^{p}+1\text{ mod }p^{2}$, and the problem is solved. Thus, it remains to show that $\binom{2p}{p}\equiv 2\text{ mod }p^{2}$. One possible way to do this is the following: For every integer $k$ with $1\leq k\leq p-1$, we have $p\mid\binom{p}{k}$ and thus $p^{2}\mid\binom{p}{k}^{2}$, so that $\binom{p}{k}^{2}\equiv 0\text{ mod }p^{2}$. Now remember the combinatorial identity $\binom{2n}{n}=\sum_{k=0}^{n}\binom{n}{k}^{2}$. Applying it to $n=p$, we get $\binom{2p}{p}=\sum_{k=0}^{p}\binom{p}{k}^{2}=\binom{p}{0}^{2}+\sum_{k=1}^{p-1}\binom{p}{k}^{2}+\binom{p}{p}^{2}$ $\equiv \binom{p}{0}^{2}+\sum_{k=1}^{p-1}0+\binom{p}{p}^{2}=1^{2}+0+1^{2}=2\text{ mod }p^{2}$. Proof complete. PS. The prime $p$ needs not be odd. darij

Peter wrote: Suppose that $ p$ is an odd prime. Prove that \[ \sum_{i = 0}^{p}\binom{p}{i}\binom{p + i}{i}\equiv 2^{p} + 1\pmod{p^{2}}. \] I have a different approach leading to other possible generalizations (It is actually generalizing the Lemma from the second proof of Putnam 1991/B4 from the PEN bi-week file). We begin with a preliminary result (which actually does all the work): Theorem 1. Let $ x$, $ y$ be real numbers, and let $ p$, $ q$ be two positive integers. Then the following identity holds \[ \sum_{i = 0}^{p}{\binom{p}{i}\binom{q + i}{i}x^{p - i}y^{i}} = \sum_{i = 0}^{p}{\binom{p}{i}\binom{q}{i}(x + y)^{p - i}y^{i}. }\] Proof. Let $ m$, $ n$ be two real numbers. Consider the identity: \[ E: = \left[(x + y)m + y\right]^{p}(1 + m)^{q} = \left(\sum_{i = 0}^{p}{\binom{p}{i}\left(x + y\right)^{p - i}m^{p - i}y^{i}}\right)\left(\sum_{i = 0}^{q}{\binom{q}{i}m^{i}}\right). \] The coefficient of $ m^{p}$ from the right hand side of the identity is $ B: = \sum_{i = 0}^{p}{\binom{p}{i}\binom{q}{i}(x + y)^{p - i}y^{i}}$. On other hand, since \[ E = \left[mx + y(1 + m)\right]^{p}(1 + m)^{q} = \sum_{i = 0}^{p}{\binom{p}{i}x^{p - i}m^{p - i}y^{i}(1 + m)^{q + i}}, \] the coefficient of $ m^{p}$ is also equal to $ A: = \sum_{i = 0}^{p}{\binom{p}{i}\binom{q + i}{i}x^{p - i}y^{i}}$, and therefore $ A = B$, which proves Theorem 1. Returning to our problem, set $ x = y = 1$, and let $ q = p$ be a prime number. In this case, \[ \sum_{i = 0}^{p}\binom{p}{i}\binom{p + i}{i} = \sum_{i = 0}^{p}{\binom{p}{i}\binom{p}{i}2^{p - i} = 1 + 2^{p} + \sum_{i = 1}^{p - 1}{\binom{p}{i}^{2}2^{p - i} \equiv 2^{p} + 1\pmod{p^{2}}. }}\] This completes the proof of our problem.

Nice, but you are free to delete all appearances of the word "nonzero" from your post. $ 0^0$ is defined to be $ 1$, this is not a matter of discussion. You can still mention that $ 0^0$ should be $ 1$, but don't let this impose unnecessary restrictions in your theorems. darij

Done. Thanks.

If $ 0<j<p$, then $ p|\binom{p}{j}, \ \ \binom{p+j}{j}=1\mod p.$ Therefore \[ \sum_{j=0}^p\binom{p}{j}\binom{p+j}{j}=2^p-2+1(j=0)+\binom{2p}{p}(j=p)\mod p^2.\] Because for odd prime $ \binom{ap}{bp}=\binom{a}{b}\mod p^3$, we get $ \sum_j\binom{p}{j}\binom{p+j}{j}=2^p+1\mod p^2.$

Rust wrote: Because for odd prime $ \binom{ap}{bp} = \binom{a}{b}\mod p^3$ How do you prove this?

It is known fact, and don't hard to prove (but long).

I want to prove it combinatorially. I'm a combinatorist, sue me. The left hand side counts the number of pairs of sets $ (X,Y)$ where $ X$ is a subset of $ \{1,\ldots,p\}$, $ Y$ is a subset of $ \{1,\ldots,2p\}$, $ |X|=|Y|$ and $ Y\subset X\cup\{p+1,\ldots,2p\}$. Consider the subgroup $ G$ of $ S_{2p}$ generated by $ (1,2,\ldots,p)$ and $ (p+1,\ldots,2p)$. $ G$ acts naturally on the above set of pairs. The count of such pairs is equivalent $ (mod |G|=p^2)$ to the count of such pairs that have a non-trivial stabilizer. If a pair has a non-trivial stabilizer, then for some $ S$ in $ \{\{1,\ldots,p\},\{p+1,\ldots,2p\}\}$, ($ S\subset X$ or $ S\cap X=\emptyset$) and ($ S\subset Y$ or $ S\cap Y=\emptyset$). Take each potential $ S$ at a time. For $ S=\{1,\ldots,p\}$, since $ X\subset S$, either $ X=S$ or $ X=\emptyset$. If $ X=\emptyset$, then since $ |X|=|Y|$, $ Y=\emptyset$. If $ X=S$, then $ |Y|=p$. Now since $ Y$ either contains $ S$ or misses $ S$, it follows that $ Y=S$ or $ Y=\{p+1,\ldots,2p\}$. For $ S=\{p+1,\ldots,2p\}$, we already know that $ X$ misses $ S$. Thus the condition is either that $ Y$ contains $ S$ or $ Y$ misses $ S$. Since $ Y$ is contained in $ S\cup X$, $ Y=X$ or $ Y$ contains $ S$. If $ Y$ contains $ S$ then $ Y=\{p+1,\ldots,2p\}$ and $ X=\{1,\ldots,p\}$. Thus we have shown that the elements with a non-trivial stabiliser are precisely the pairs $ (X,X)$ for subsets $ X$ of $ \{1,\ldots,p\}$ and $ (\{1,\ldots,p\},\{p+1,\ldots,2p\})$. Thus there are $ 2^p+1$ of them. Luke See my puzzle blog at http://bozzball.blogspot.com

I did it the following way. Let $ A=\{a_1$, $ a_2$, $ \dots$, $ a_p\}$ and $ B=\{b_1$, $ b_2$, $ \dots$, $ b_p\}$. For any $ 0 \le j \le p$, we choose a set $ A_j$ consisting of $ p-j$ distinct elements from $ A$ and color them green. Then we choose $ j$ elements from the union $ (A \setminus A_k) \cup B$ and color them red. Hence we've chosen $ p$ elements in total. If we sum up over all $ 0 \le j \le p$, we get the desired sum. Next, for any $ 0 \le k \le p$, choose $ k$ elements from $ A$ and $ p-k$ elements from $ B$. Color each of the $ p-k$ elements red. For each of the $ k$ elements, there are two possibilities, namely it is red or green. Hence there are in total $ 2^k$ possibilities to color the $ k$ elements chosen from $ A$. This gives $ 2^k \binom{p}{k} \binom{p}{p-k}$ possibilities for every $ k$. If we sum up over all $ 0 \le k \le p$, we get $ \sum_{k=0}^{p} 2^k \binom{p}{k}^2$ possibilities. It's easy to see that the above "operations" of choosing and coloring the elements are equivalent. Hence the two sums are equal. The conclusion follows, as $ \binom{p}{j}^2 \equiv 0 \mod p^2$ for every $ 0<j<p$. (I hope it's not the same as another solution, but, to be honest, I didn't read them...^^)

dule_00 wrote: Rust wrote: Because for odd prime $ \binom{ap}{bp} = \binom{a}{b}\mod p^3$ How do you prove this? In fact, we don't need Wolstenholme's theorem or its proof here. Just note: \[\binom{2p}p=\sum_{i=0}^p\binom p i^2\equiv2\mod p^2\] This is because $p|\binom p i$ for $0<i<p$. Moreover the theroem is true if $p>3$ Rust wrote: If $ 0<j<p$, then $ p|\binom{p}{j}, \ \ \binom{p+j}{j}=1\mod p.$ Therefore \[ \sum_{j=0}^p\binom{p}{j}\binom{p+j}{j}=2^p-2+1(j=0)+\binom{2p}{p}(j=p)\mod p^2.\] Because for odd prime $ \binom{ap}{bp}=\binom{a}{b}\mod p^3$, we get $ \sum_j\binom{p}{j}\binom{p+j}{j}=2^p+1\mod p^2.$ I didn't get the point why $\binom{p+i}i\equiv1\mod p$ implies \[ \sum_{j=0}^p\binom{p}{j}\binom{p+j}{j}=2^p-2+1(j=0)+\binom{2p}{p}(j=p)\mod p^2.\] The second modulo is taken over $p^2$ whereas the first modulo was for $p$.

I used the modulo lemma for rational numbers which is : $1/q=x$(mod p ) in which gcd (p,q)=1 and $xq=1$ (mod p )

It is known that \(\binom{2p}p\equiv2\pmod{p^2}\). Now the following claim will suffice: Claim: For \(i=0,1,\ldots,p-1\), \[\binom{p+i}i\binom pi\equiv\binom pi\pmod{p^2}.\] Proof. The claim obviously holds for \(i=0\), so assume \(i\ge1\). Then, \(p\mid\binom pi\) and \[\binom{p+i}i\equiv\frac{(p+i)\cdots(p+1)}{i\cdots1}\equiv\frac{i\cdots1}{i\cdots1}\equiv1\pmod p.\]\(\blacksquare\) Finally, \[\sum_{i=0}^p\binom{p+i}i\binom pi\equiv1+\sum_{i=0}^p\binom pi\equiv2^p+1\pmod p.\]

Claim. We have $p\left(\sum_{i=1}^{p-1} (-1)^{i+1} \cdot \dfrac{1}{i} \right)\equiv 2\left(2^{p-1}-1\right)\pmod{p^2}.$ Proof. We use the following relation: \begin{align*} \frac{1}{p} \binom{p}{k} &=\frac{(p-1)(p-2)\ldots(p-k+1)}{k(k-1)\ldots 1}\\& \equiv \frac{(-1)(-2)\ldots(-k+1)}{k(k-1)\ldots 1}\\&\equiv (-1)^{k-1} \frac{1}{k} \pmod{p}\\ \end{align*}Thus, we need $$\sum_{i=1}^{p-1} \binom{p}{i} \equiv 2\left(2^{p-1}-1\right)\pmod{p^2},$$but this is obvious as $$\sum_{i=1}^{p-1} \binom{p}{i} =\sum_{i=0}^{p} \binom{p}{i} -\binom{p}{0} -\binom{p}{p}=2^p-2=2(2^{p-1}-1).$$The claim follows. \(\square\) Claim. For \(i=1,\ldots,p-1\), $\dfrac{(p+i)!}{(p-i)!(i!)^2}\equiv (-1)^{i-1}\frac{p}{i}\pmod{p^2}$ Proof. \begin{align*}\dfrac{(p+i)!}{(p-i)!(i!)^2}&\equiv\dfrac{(p+i)(p+i-1)\ldots (p-i+1)}{(i!)^2}\\&\equiv \dfrac{(p^2+pi)(p^2-(i-1)^2)\ldots(p^2-1^2)}{(i!)^2}\\&\equiv \dfrac{(pi)(-(i-1)^2)\ldots(-1^2)}{(i!)^2}\\&\equiv(-1)^{i-1}\frac{p}{i}\pmod{p^2}.\end{align*}The claim follows. \(\square\) Thus, $$\sum_{i=0}^{p}\binom{p}{i}\binom{p+i}{i}\equiv\sum_{i=0}^{p}\dfrac{(p+i)!}{(p-i)!(i!)^2}\equiv\sum_{i=1}^{p-1}\dfrac{(p+i)!}{(p-i)!(i!)^2}+3 \equiv2^{p}+1\pmod{p^{2}}.$$

Lagrange theorem