Controlled $R_{k}$ gates are implemented in the quantum Fourier transform as shown here:
Each of the $R_{k}$ on a qubit is in this matrix form: $$\begin{pmatrix}1 & 0 \\ 0 & e^{2\pi i/2^k}\end{pmatrix}$$
My question is: Why can each of these controlled $R_{k}$ gates, no matter what $k$ is, be produced by two controlled-Not gates? (I think the global phase can be ignored)
Let $|0_m\rangle$, $|1_m\rangle$ be the computational basis for qubit $m$. Also, denote $R_k^{(m)}$ the $R_k$ gate acting on qubit $m$ and $CR_k^{(m,n)}$ the controlled-$R_k$ gate acting on $m$ and using $n$ as ancilla.
Things are easier to see if you write down explicitly the action of $CR_k^{(m,n)}$ on qubits $m$ and $n$, using the action of $R_k^{(m)}$. We have: $$ R_k^{(m)}|0_m\rangle = |0_m\rangle \\ R_k^{(m)}|1_m\rangle = e^{\frac{2\pi i}{2^k}}|1_m\rangle $$ and, for an arbitrary state $|\psi_{mn}\rangle = a_{00}|0_m 0_n\rangle + a_{10}|1_m 0_n\rangle + a_{01}|0_m 1_n\rangle + a_{11}|1_m 1_n\rangle$, $$ CR_k^{(m,n)}|\psi_{mn}\rangle = a_{00}|0_m 0_n\rangle + a_{10}|1_m 0_n\rangle + a_{01}|0_m 1_n\rangle + a_{11}e^{\frac{2\pi i}{2^k}}|1_m 1_n\rangle $$ We want to construct $CR_k^{(m,n)}$ using the $CNOT^{(m,n)}$ gate that targets $m$ and has $n$ as ancilla. Let's write down the action of $CNOT^{(m,n)}$ on $|\psi_{mn}\rangle$: $$ CNOT^{(m,n)}|\psi_{mn}\rangle = a_{00}|0_m 0_n\rangle + a_{10}|1_m 0_n\rangle + a_{11}|0_m 1_n\rangle + a_{01}|1_m 1_n\rangle $$ If we assume that there does exist some sequence of gates involving $CNOT^{(m,n)}$ that reproduces $CR_k^{(m,n)}$, it is pretty obvious that applying $CNOT^{(m,n)}$ only once will redistribute the $a_{10}$ and $a_{11}$ coefficients to the wrong basis states. This means that any equivalent gate sequence must apply $CNOT^{(m,n)}$ at least twice or, in general, an even number of times. Fortunately there is at least one sequence that reproduces $CR_k^{(m,n)}$ using $CNOT^{(m,n)}$ only twice.
However, by itself $CNOT^{(m,n)}$ does not help much, since it cannot produce the needed phase factor in the last term of $|\psi_{mn}\rangle$. The only way to get the phase is to apply $R_k^{(m)}$ before $CNOT^{(m,n)}$ because we need to attach said phase to the correct $a_{11}$ coefficient. In other words, the sequence for $CR_k^{(m,n)}$ must also contain at least one factor $R_k^{(m)}$, not only the two factors of $CNOT^{(m,n)}$. It turns out that the minimal sequence uses not $R_k$, but $R_{k+1}$, and does so three times: twice on $m$ and once on $n$.
The reason is that the action of $R_k^{(m)}$ on $|\psi_{mn}\rangle$ reads $$ R_k^{(m)}|\psi_{mn}\rangle = a_{00}|0_m 0_n\rangle + a_{10}e^{\frac{2\pi i}{2^k}}|1_m 0_n\rangle + a_{01}|0_m 1_n\rangle + a_{11}e^{\frac{2\pi i}{2^k}}|1_m 1_n\rangle $$ and we must find a way to get rid of the extra phase attached to $a_{10}$. One way to do this is to take $$ CR_k^{(m,n)} = CNOT^{(m,n)} \left( R_{k+1}^{(m)} \right)^\dagger CNOT^{(m,n)} R_{k+1}^{(n)} R_{k+1}^{(m)} $$
Let's check that it works: $$ CNOT^{(m,n)} \left( R_{k+1}^{(m)} \right)^\dagger CNOT^{(m,n)} R_{k+1}^{(n)} R_{k+1}^{(m)}|\psi_{mn}\rangle = \\ = CNOT^{(m,n)} \left( R_{k+1}^{(m)} \right)^\dagger CNOT^{(m,n)} R_{k+1}^{(n)}\left[ a_{00}|0_m 0_n\rangle + a_{10}e^{\frac{2\pi i}{2^{k+1}}}|1_m 0_n\rangle + a_{01}|0_m 1_n\rangle + a_{11}e^{\frac{2\pi i}{2^{k+1}}}|1_m 1_n\rangle \right] =\\ = CNOT^{(m,n)} \left( R_{k+1}^{(m)} \right)^\dagger CNOT^{(m,n)} \left[ a_{00}|0_m 0_n\rangle + a_{10}e^{\frac{2\pi i}{2^{k+1}}}|1_m 0_n\rangle + e^{\frac{2\pi i}{2^{k+1}}}a_{01}|0_m 1_n\rangle + a_{11}e^{\frac{2\pi i}{2^{k+1}}+\frac{2\pi i}{2^{k+1}}}|1_m 1_n\rangle \right] = \\ = CNOT^{(m,n)} \left( R_{k+1}^{(m)} \right)^\dagger \left[ a_{00}|0_m 0_n\rangle + a_{10}e^{\frac{2\pi i}{2^{k+1}}}|1_m 0_n\rangle + e^{\frac{2\pi i}{2^k}}a_{11}|0_m 1_n\rangle + a_{01}e^{\frac{2\pi i}{2^{k+1}}}|1_m 1_n\rangle \right] = \\ = CNOT^{(m,n)} \left[ a_{00}|0_m 0_n\rangle + a_{10}e^{-\frac{2\pi i}{2^{k+1}}} e^{\frac{2\pi i}{2^{k+1}}}|1_m 0_n\rangle + e^{\frac{2\pi i}{2^k}}a_{11}|0_m 1_n\rangle + a_{01}e^{-\frac{2\pi i}{2^{k+1}}} e^{\frac{2\pi i}{2^{k+1}}}|1_m 1_n\rangle \right] = \\ = CNOT^{(m,n)} \left[ a_{00}|0_m 0_n\rangle + a_{10}|1_m 0_n\rangle + e^{\frac{2\pi i}{2^k}}a_{11}|0_m 1_n\rangle + a_{01}|1_m 1_n\rangle \right] =\\ = a_{00}|0_m 0_n\rangle + a_{10}|1_m 0_n\rangle + a_{01}|0_m 1_n\rangle + e^{\frac{2\pi i}{2^k}}a_{11}|1_m 1_n\rangle = CR_k^{(m,n)}|\psi_{mn}\rangle $$
Q.e.d.
