Replacing fermionic operators with their Fourier transform and boundary conditions In the section 4.1 of Quantum Computation by Adiabatic Evolution, Farhi et al proposes a quantum adiabatic algorithm to solve the $2$-SAT problem on a ring. To compute the complexity of the algorithm the authors computed the energy gap between the ground and first excited states of the 
adiabatic Hamiltonian.
The adiabatic Hamiltonian is defined as 
$$
\tilde{H} (s) = (1-s) \sum^n_{j=1}(1-\sigma^{(j)}_x) + s \sum^n_{j=1}\frac{1}{2} (1-\sigma^{(j)}_z \sigma^{(j+1)}_z )
$$
Then the adiabatic Hamiltonian is reexpressed using fermionic operators as follows.
$$
\tilde{H}(s) = \sum^n_{j=1} \left\{2 (1-s)b^\dagger_j b_j + \frac{s}{2}(1-(b^\dagger_j - b_j)(b^\dagger_{j+1} + b_{j+1}))\right\}
$$
Then the authors takes the Fourier transform of the fermionic operators,
$$\beta_p =  \frac{1}{\sqrt{n}} \sum^n_{j=1} e^{i\pi p j/n} b_j$$
where $p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)$,
and rewrite the adiabatic Hamiltonian as
$$\tilde{H}(s) = \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} A_p (s)$$
where
$$
A_p (s) = 2 (1-s)[\beta^\dagger_p \beta_p + \beta^\dagger_{-p} \beta_{-p}] + s \left\{1 - \cos\frac{\pi p}{n} [\beta^\dagger_p \beta_p - \beta_{-p} \beta^\dagger_{-p}] + i \sin \frac{\pi p}{n}[\beta^\dagger_{-p} \beta^\dagger_{p} - \beta_{p} \beta_{-p}]\right\}.
$$
My question:
How can I derive the second part i.e. $s \left\{1 - \cos\frac{\pi p}{n} [\beta^\dagger_p \beta_p - \beta_{-p} \beta^\dagger_{-p}] + i \sin \frac{\pi p}{n}[\beta^\dagger_{-p} \beta^\dagger_{p} - \beta_{p} \beta_{-p}]\right\}$?
My attempt:
We compute few quantities.
$$
\beta^\dagger_p \beta_p = \left(\frac{1}{\sqrt{n}}\sum^n_{k=1}e^{-i\pi p k/n}b^\dagger_k\right)\left(\frac{1}{\sqrt{n}}\sum^n_{j=1}e^{i\pi p j/n}b_j\right)
\\
=\frac{1}{n} \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b^\dagger_k b_j
$$,
$$
\beta^\dagger_{-p} \beta_{-p} = \left(\frac{1}{\sqrt{n}} \sum^n_{k=1} e^{i\pi p k/n} b^\dagger_k\right)\left(\frac{1}{\sqrt{n}} \sum^n_{j=1} e^{-i\pi p j/n} b_j\right)
\\
=\frac{1}{n} \sum^n_{k,j=1}e^{i\pi p (k-j)/n} b^\dagger_k b_j
$$,
$$
\beta_{-p} \beta^\dagger_{-p} = \left( \frac{1}{\sqrt{n}} \sum^n_{j=1} e^{-i\pi p j/n} b_j\right)\left( \frac{1}{\sqrt{n}} \sum^n_{k=1} e^{i\pi p k/n} b^\dagger_k\right)
\\
=\frac{1}{n} \sum^n_{k,j=1}e^{i\pi p (k-j)/n} b_j b^\dagger_k
$$,
$$
\beta^\dagger_{-p} \beta^\dagger_{p} = \left(\frac{1}{\sqrt{n}} \sum^n_{j=1} e^{i\pi p j/n} b^\dagger_j\right)\left(\frac{1}{\sqrt{n}} \sum^n_{k=1} e^{-i\pi p k/n} b^\dagger_k\right)
\\
=\frac{1}{n} \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b^\dagger_j b^\dagger_k
$$, 
and
$$
\beta_{p} \beta_{-p} = \left(\frac{1}{\sqrt{n}} \sum^n_{j=1} e^{i\pi p j/n} b_j\right)\left(\frac{1}{\sqrt{n}} \sum^n_{k=1} e^{-i\pi p k/n} b_k\right)
\\
=\frac{1}{n} \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b_j b_k
$$.
We also compute two linear combinations of these quantities.
\begin{align}
\beta^\dagger_{p} \beta_{p} - \beta_{-p} \beta^\dagger_{-p} &=  \frac{1}{n} \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b^\dagger_k b_j - \frac{1}{n} \sum^n_{k,j=1}e^{i\pi p (k-j)/n} b_j b^\dagger_k
\nonumber\\
&=  \frac{1}{n} \left( \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b^\dagger_k b_j -  \sum^n_{k,j=1}e^{i\pi p (k-j)/n} b_j b^\dagger_k\right)
\nonumber\\
&=  \frac{1}{n} \left( \sum^n_{k,j=1}\left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_k b_j \right.
\nonumber\\
& \left. -  \sum^n_{k,j=1} \left(\cos \left(\pi p (k-j)/n\right) + i \sin \left(\pi p (k-j)/n\right) \right) b_j b^\dagger_k\right)
\nonumber\\
&=  \frac{1}{n}  \sum^n_{k,j=1} \left(\left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_k b_j \right.
\nonumber\\
& \left. -  \left(\cos \left(\pi p (k-j)/n\right) + i \sin \left(\pi p (k-j)/n\right) \right) b_j b^\dagger_k\right)
\end{align}
and
\begin{align}
\beta^\dagger_{-p} \beta^\dagger_{p} - \beta_{p} \beta_{-p} &=  \frac{1}{n} \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b^\dagger_j b^\dagger_k - \frac{1}{n} \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b_j b_k
\nonumber\\
&=  \frac{1}{n} \left( \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b^\dagger_j b^\dagger_k -  \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b_j b_k\right)
\nonumber\\
&=  \frac{1}{n} \left( \sum^n_{k,j=1}\left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_j b^\dagger_k \right.
\nonumber\\
& \left.-  \sum^n_{k,j=1}\left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b_j b_k\right)
\nonumber\\
&=  \frac{1}{n} \sum^n_{k,j=1} \left( \left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_j b^\dagger_k \right.
\nonumber\\
& \left.- \left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b_j b_k\right)
\end{align}.
So, 
\begin{align}
1 - \cos \frac{\pi p}{n}\left[\beta^\dagger_p \beta_p - \beta_{-p}  \beta^\dagger_{-p}\right] + i \sin \frac{\pi p}{n} \left[\beta^\dagger_{-p} \beta^\dagger_p - \beta_p \beta_{-p}\right] =
\nonumber\\
 1 - \cos \frac{\pi p}{n}\left[\frac{1}{n}  \sum^n_{k,j=1} \left(\left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_k b_j \right. \right.
\nonumber\\
 -  \left. \left.  \left(\cos \left(\pi p (k-j)/n\right) + i \sin \left(\pi p (k-j)/n\right) \right) b_j b^\dagger_k\right)\right] 
 \nonumber\\
 + i \sin \frac{\pi p}{n} \left[\frac{1}{n} \sum^n_{k,j=1} \left( \left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_j b^\dagger_k \right. \right.
  \nonumber\\
 - \left. \left. \left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b_j b_k\right)\right]
 \nonumber\\
= 1 - \frac{1}{n} \cos \frac{\pi p}{n}\left[  \sum^n_{k,j=1} \left(\left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_k b_j \right. \right.
\nonumber\\
 -  \left. \left.  \left(\cos \left(\pi p (k-j)/n\right) + i \sin \left(\pi p (k-j)/n\right) \right) b_j b^\dagger_k\right)\right] 
 \nonumber\\
 + \frac{1}{n}i \sin \frac{\pi p}{n} \left[ \sum^n_{k,j=1} \left( \left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_j b^\dagger_k \right. \right.
  \nonumber\\
 - \left. \left. \left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b_j b_k\right)\right]
  \nonumber\\
= 1 - \frac{1}{n} \left[  \sum^n_{k,j=1} \left(\left(\cos \frac{\pi p}{n} \cos \left(\pi p (k-j)/n\right) - i\cos \frac{\pi p}{n} \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_k b_j \right. \right.
\nonumber\\
 -  \left. \left.  \left(\cos \frac{\pi p}{n} \cos \left(\pi p (k-j)/n\right) + i \cos \frac{\pi p}{n} \sin \left(\pi p (k-j)/n\right) \right) b_j b^\dagger_k\right)\right] 
 \nonumber\\
 + \frac{1}{n}i  \left[ \sum^n_{k,j=1} \left( \left(\sin \frac{\pi p}{n} \cos \left(\pi p (k-j)/n\right) - i \sin \frac{\pi p}{n} \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_j b^\dagger_k \right. \right.
  \nonumber\\
 - \left. \left. \left(\sin \frac{\pi p}{n} \cos \left(\pi p (k-j)/n\right) - i \sin \frac{\pi p}{n} \sin \left(\pi p (k-j)/n\right)\right) b_j b_k\right)\right]
\end{align}
I am not sure how to get to $1-(b^\dagger_j - b_j)(b^\dagger_{j+1} + b_{j+1})$ from here.
Update 1:
Following the comment by @mas, I am starting with Eq. 4.14 i.e. the inverse Fourier transform.
\begin{align}
b_j &=  \frac{1}{\sqrt{n}} \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p j/n} \beta_p
\end{align}
So, 
$$
\sum^n_{j=1} (b^\dagger_j - b_j)(b^\dagger_{j+1} + b_{j+1}) = \\
\sum^n_{j=1}  (\frac{1}{\sqrt{n}} \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p j/n} \beta^\dagger_p - \frac{1}{\sqrt{n}} \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p j/n} \beta_p)(\frac{1}{\sqrt{n}} \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p (j+1)/n} \beta^\dagger_p + \frac{1}{\sqrt{n}} \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p (j+1)/n} \beta_p)
\\
=\sum^n_{j=1}  \frac{1}{n} ( \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p j/n} \beta^\dagger_p -  \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p j/n} \beta_p)( \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p (j+1)/n} \beta^\dagger_p +  \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p (j+1)/n} \beta_p)
\\
=\sum^n_{j=1}  \frac{1}{n} ( \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p j/n} \beta^\dagger_p \sum_{q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi q (j+1)/n} \beta^\dagger_q -  \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p j/n} \beta_p \sum_{q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi q (j+1)/n} \beta^\dagger_q + \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p j/n} \beta^\dagger_p \sum_{q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi q (j+1)/n} \beta_q -  \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p j/n} \beta_p \sum_{q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi q (j+1)/n} \beta_q)
\\
=\sum^n_{j=1}  \frac{1}{n} ( \sum_{p,q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p j/n}   e^{i\pi q (j+1)/n} \beta^\dagger_p \beta^\dagger_q -  \sum_{p,q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p j/n}   e^{i\pi q (j+1)/n} \beta_p \beta^\dagger_q + \sum_{p,q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p j/n}   e^{-i\pi q (j+1)/n} \beta^\dagger_p \beta_q -  \sum_{p,q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p j/n}   e^{-i\pi q (j+1)/n} \beta_p \beta_q)
$$
I am still stuck.
 A: \begin{equation}
b_{j} = \frac{1}{\sqrt{n}}\sum_{p}e^{-i\pi pj/n}\beta_{p}\qquad b_{j+1} = \frac{1}{\sqrt{n}}\sum_{p}e^{-i\pi q(j+1)/n}\beta_{q}
\end{equation}
Then
\begin{equation}
b_{j}^{\dagger}b_{j+1}^{\dagger} = \frac{1}{n}\sum_{p,q}e^{\pi i(p+q)j/n}e^{\pi iq/n}\beta_{q}^{\dagger}\beta_{p}^{\dagger} = \sum_{p} e^{-\pi ip/n}\beta_{-p}^{\dagger}\beta_{p}^{\dagger}
\end{equation}
Likewise $b_{j}b_{j+1}= \sum_{p} e^{\pi ip/n}\beta_{-p}\beta_{p}$. Then
\begin{eqnarray}
b_{j}^{\dagger}b_{j+1}^{\dagger}-b_{j}b_{j+1} & = & \sum_{p} [e^{-\pi ip/n}\beta_{-p}^{\dagger}\beta_{p}^{\dagger}-e^{\pi ip/n}\beta_{-p}\beta_{p}] \\
& = & \sum_{p}e^{-\pi ip/n}[\beta_{-p}^{\dagger}\beta_{p}^{\dagger}-e^{2\pi ip/n}\beta_{-p}\beta_{p}]\\
& = & \sum_{p}e^{-\pi ip/n}[\beta_{-p}^{\dagger}\beta_{p}^{\dagger}-\beta_{-p}\beta_{p}]\quad\boxed{\text{using}~e^{2\theta}=1}\\
& = & \sum_{p}(\cos\frac{\pi p}{n}-i\sin\frac{\pi p}{n})[\beta_{-p}^{\dagger}\beta_{p}^{\dagger}-\beta_{-p}\beta_{p}]\\
& = & -2i\sum_{p}\sin\left(\frac{\pi p}{n}\right)[\beta_{-p}^{\dagger}\beta_{p}^{\dagger}-\beta_{-p}\beta_{p}] \\
\Rightarrow -\frac{1}{2}[b_{j}^{\dagger}b_{j+1}^{\dagger}-b_{j}b_{j+1}] & = & i\sum_{p}\sin\left(\frac{\pi p}{n}\right)[\beta_{-p}^{\dagger}\beta_{p}^{\dagger}-\beta_{-p}\beta_{p}] \\
\end{eqnarray}
Which is the desired expression. Lets check the term $\sum_{p}(\cos\frac{\pi p}{n}-i\sin\frac{\pi p}{n})[\beta_{-p}^{\dagger}\beta_{p}^{\dagger}-\beta_{-p}\beta_{p}]$ for $p=\pm 1$ (setting $\frac{1}{n}=m$)
\begin{eqnarray}
(\cos\pi m-i\sin\pi m)[\beta_{-1}^{\dagger}\beta_{1}^{\dagger}-\beta_{-1}\beta_{1}]+[\cos(-\pi m)-i\sin(-\pi m)][\beta_{1}^{\dagger}\beta_{-1}^{\dagger}-\beta_{1}\beta_{-1}] & = & -2i\sin(\pi m)[\beta_{-1}^{\dagger}\beta_{1}^{\dagger}-\beta_{-1}\beta_{1}]
\end{eqnarray}
(There $b_{-p}b_{p}=-b_{p}b_{-p}$ has been used). Therefore no contribution comes from cosine terms. Likewise rest of the expression follows.
