# How to prove $\sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k}\sum_{i=\lfloor k/2\rfloor +1}^k\frac{1}{2i-1}\equiv 0\pmod{p}$?

Numerical calculation suggests that for prime $p\ge 5$, \begin{align*} \sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k}\sum_{i=\lfloor k/2\rfloor +1}^k\frac{1}{2i-1}\equiv 0\pmod{p}. \end{align*}

Question. How can we prove this congruence?

It turned out the OP's question required a good amount of work and a joint effort (with Roberto Tauraso). However, "the margin here is too small to contain the proof", so to say.

• Little comment: $p'$ is used before it is defined. Congrats on solving this! (I spent some hours to no avail.) – darij grinberg Jun 21 '17 at 22:05
• @ Professor Amdeberhan: Thank you very much for your great efforts to solve this problem. Thanks also go to Professor Tauraso. – Ji-Cai Liu Jun 26 '17 at 10:54

This is complementary to the note by Amdeberhan and Tauraso. In order to solve this problem, Amdeberhan and Tauraso [Equations (12) and (15)] established the following two important results: \begin{align} &\sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k}H_k\equiv \frac{1}{2}q_p(2)^2+(-1)^{\frac{p-1}{2}}E_{p-3}\pmod{p},\tag{1}\\ &\sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k}H_{2k}\equiv \frac{1}{4}q_p(2)^2\pmod{p},\tag{2} \end{align} for primes $p\ge 5$. Here $H_n$ denotes the $n$-th harmonic number, $E_n$ denotes the $n$-th Euler number, and the Fermat quotient of an integer $a$ with respect to an odd prime $p$ is given by $q_p(a)=(a^{p-1}-1)/p$.

We shall give alternative proofs of (1) and (2) by use of combinatorial identities.

Proof of (1). For $0\le k\le p-1$, we have \begin{align*} {p-1\choose k}=\frac{(p-1)(p-2)\cdots(p-k)}{k!}\equiv (-1)^k+p(-1)^{k-1}H_k\pmod{p^2}, \end{align*} and so \begin{align} (-1)^kH_k\equiv \frac{1}{p}\left((-1)^k-{p-1\choose k}\right)\pmod{p}.\tag{3} \end{align} It follows that \begin{align} \sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^{k-1}}{k}H_{k-1} &\equiv -\frac{1}{p}\left(\sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k} +\sum_{k=1}^{\frac{p-1}{2}}\frac{1}{k}{p-1\choose k-1}\right)\pmod{p}.\tag{4} \end{align}

Note that \begin{align} \sum_{k=1}^{\frac{p-1}{2}}\frac{1}{k}{p-1\choose k-1} =\frac{1}{p}\sum_{k=1}^{\frac{p-1}{2}}{p\choose k} =\frac{1}{2p}\left(\sum_{k=0}^{p-1}{p\choose k}-2\right)=q_p(2).\tag{5} \end{align} Next, we shall prove that \begin{align} \sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k}\equiv -q_p(2)+\frac{p}{2}q_p(2)^2-p(-1)^{\frac{p-1}{2}}E_{p-3}\pmod{p^2}.\tag{6} \end{align} By Lehmer's congruence [Ann. Math. 39 (1938), 350--360, (45)], we deduce that \begin{align} \sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k}= \sum_{k=1}^{\lfloor p/4\rfloor}\frac{1}{k}-\sum_{k=1}^{\frac{p-1}{2}}\frac{1}{k} \equiv \sum_{k=1}^{\lfloor p/4\rfloor}\frac{1}{k}+2q_p(2)-pq_p(2)^2\pmod{p^2},\tag{7} \end{align} where $\lfloor x \rfloor$ denotes the greatest integer less than or equal to a real number $x$. Another congruence due to Lehmer [Ann. Math. 39 (1938), 350--360, (43)] says \begin{align} \sum_{k=1}^{\lfloor p/4\rfloor}\frac{1}{p-4k}\equiv \frac{3}{4}q_p(2)-\frac{3}{8}pq_p(2)^2\pmod{p^2}.\tag{8} \end{align} For $0\le k \le\lfloor\frac{p}{4}\rfloor$, we have \begin{align*} \frac{1}{p-4k}\equiv -\frac{1}{4k}-\frac{p}{16k^2}\pmod{p^2}. \end{align*} Substituting the above into (8) gives \begin{align} \sum_{k=1}^{\lfloor p/4\rfloor}\frac{1}{k}\equiv -3q_p(2)+\frac{3}{2}pq_p(2)^2-\frac{p}{4}\sum_{k=1}^{\lfloor p/4 \rfloor}\frac{1}{k^2}\pmod{p^2}.\tag{9} \end{align} By [Ann. Math. 39 (1938), 350--360, (48)], we have \begin{align} \sum_{k=1}^{\lfloor p/4\rfloor}\frac{1}{k^2}\equiv 4(-1)^{\frac{p-1}{2}}E_{p-3}\pmod{p}.\tag{10} \end{align} Combining (7), (9) and (10), we are led to (6).

Applying (5) and (6) to the right-hand side of (4), we obtain \begin{align} \sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^{k-1}}{k}H_{k-1} \equiv -\frac{1}{2}q_p(2)^2+(-1)^{\frac{p-1}{2}}E_{p-3}\pmod{p}.\tag{11} \end{align} Sun [Sci. China Math. 54 (2011), 2509--2535, Lemma 2.4] showed that \begin{align} \sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k^2}\equiv (-1)^{\frac{p-1}{2}}2E_{p-3}\pmod{p}.\tag{12} \end{align} From the above and (11), we deduce that \begin{align*} \sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^{k}}{k}H_{k} &=\sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^{k}}{k^2}-\sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^{k-1}}{k}H_{k-1}\\ &\equiv \frac{1}{2}q_p(2)^2+(-1)^{\frac{p-1}{2}}E_{p-3}\pmod{p}. \end{align*} The desired result is reached.

Proof of (2). By (3), we obtain that for $0\le k\le \frac{p-1}{2}$, \begin{align*} H_{2k-1}\equiv \frac{1}{p}\left(1+{p-1\choose 2k-1}\right)\pmod{p}. \end{align*} It follows that \begin{align} \sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k}H_{2k-1} \equiv \frac{1}{p}\left(\sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k} +\sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k}{p-1\choose 2k-1}\right)\pmod{p}.\tag{13} \end{align} Letting $n=\frac{p-1}{2}$ in the following identity: \begin{align*} \sum_{k=0}^n(-1)^k{2n+1\choose 2k}=(-1)^{\frac{n(n+1)}{2}}2^n, \end{align*} which can be easily proved by Zeilberger's algorithm, we find that \begin{align} \sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k}{p-1\choose 2k-1} =\frac{2}{p}\left(\sum_{k=0}^{\frac{p-1}{2}}(-1)^k{p\choose 2k}-1\right) =\frac{2}{p}\left((-1)^{\frac{p^2-1}{8}}2^{\frac{p-1}{2}}-1\right).\tag{14} \end{align}

Next, we show that \begin{align} \frac{2}{p}\left((-1)^{\frac{p^2-1}{8}}2^{\frac{p-1}{2}}-1\right) \equiv q_p(2)-\frac{p}{4}q_p(2)^2\pmod{p^2},\tag{15} \end{align} which is equivalent to \begin{align} 8(-1)^{\frac{p^2-1}{8}}2^{\frac{p-1}{2}}+\left(2^{\frac{p-1}{2}}\right)^4 -6\left(2^{\frac{p-1}{2}}\right)^2-3\equiv 0 \pmod{p^3}.\tag{16} \end{align} Note that \begin{align*} (-1)^{\frac{p^2-1}{8}}=\left(\frac{2}{p}\right), \end{align*} where $\left(\frac{\cdot}{p}\right)$ denotes the Legendre symbol. If $\left(\frac{2}{p}\right)=1$, then the left-hand side of (16) equals \begin{align*} \left(2^{\frac{p-1}{2}}+3\right)\left(2^{\frac{p-1}{2}}-1\right)^3\equiv 0 \pmod{p^3}. \end{align*} If $\left(\frac{2}{p}\right)=-1$, we find that the left-hand side of (16) equals \begin{align*} \left(2^{\frac{p-1}{2}}-3\right)\left(2^{\frac{p-1}{2}}+1\right)^3\equiv 0 \pmod{p^3}. \end{align*} Now we conclude the proof of (16).

Combining (6) and (13)--(15), we obtain \begin{align*} \sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k}H_{2k-1} \equiv \frac{1}{4}q_p(2)^2-(-1)^{\frac{p-1}{2}}E_{p-3}\pmod{p}. \end{align*} It follows from the above and (12) that \begin{align*} \sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k}H_{2k} =\sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k}H_{2k-1}+\frac{1}{2} \sum_{k=1}^{\frac{p-1}{2}}\frac{(-1)^k}{k^2}\equiv \frac{1}{4}q_p(2)^2\pmod{p}, \end{align*} which completes the proof of (2).