Inductive proof of $D_N=-H_n\cdot R_N \cdot H_n $ (Grover Iterator) I am currently working on an inductive proof $D_N=-H_n\cdot R_N \cdot H_n $ (H is the Hadamard matrix for n Bits), the induction assumption (base case) and the induction condition have been done by me, but I can not go further in the Inductive step. 
First, there are a few key details to mention:
$$D_N = \begin{pmatrix}-1+\frac{2}{N}&\frac{2}{N}&...&\frac{2}{N}\\\frac{2}{N}&-1+\frac{2}{N}&...&\frac{2}{N}\\\vdots&\vdots&\ddots&\vdots\\\frac{2}{N}&\frac{2}{N}&...&-1+\frac{2}{N}\end{pmatrix}$$
In the proof there is to shown that: $D_N=-H_n\cdot R_N \cdot H_n, \quad R_N=\begin{pmatrix}-1&0&...&0\\0&1&\ddots&\vdots\\\cdots&\ddots&\ddots&0\\0&...&0&1\end{pmatrix}$
These are my ideas:
Induction assumption (base case): $N=2, N=2^n$
$$D_2 = -H\cdot R_2 \cdot H = -\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\cdot \begin{pmatrix}-1&0\\0&1\end{pmatrix}\cdot\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix} = \begin{pmatrix}0&1\\1&0\end{pmatrix}$$
Thus:
$$D_2=\begin{pmatrix}0&1\\1&0\end{pmatrix}=\begin{pmatrix}0&1\\1&0\end{pmatrix}$$
Induction condition:
For any but firm $n$ the statement applies.
Inductive step: n+1
$$D_{N+1}=-H_{n+1}R_{N+1}H_{n+1}$$
$H_{n+1}$ is equal to $H_1\otimes H_n=\frac{1}{\sqrt{2}}\begin{pmatrix}H_n&H_n\\H_n&-H_n\end{pmatrix}$
then you would have first:
$$D_{N+1}=-\frac{1}{\sqrt{2}}\begin{pmatrix}H_n&H_n\\H_n&-H_n\end{pmatrix}\cdot R_{N+1}\cdot \frac{1}{\sqrt{2}}\begin{pmatrix}H_n&H_n\\H_n&-H_n\end{pmatrix}$$
Now, however, the question remains open, how to express or rewrite the $D_{N+1}$ and the $R_{N+1}$.
For me, in the induction step already raises the question of whether $N+1$ and $n+1$ is right at all.
I'm stuck with this step. I am grateful for the answers and hope that the question is clear and understandable.
 A: You have to notice that $N=2^{n-1}$ and you are doing induction on $n$. The induction step is that
$$-H_nR_{2^{n-1}}H_n=D_{2^{n-1}}.$$
Also notice that $R_2^{n}$ can be writen as a block matrix in the following way:
$$ R_{2^n}=\left(\begin{array}{c|c} 
R_{2^{n-1}} & 0\\
\hline
0 & I_{2^{n-1}}
 \end{array}\right). $$
And so,
$$-H_{n+1}R_{2^n}H_{n+1}=-\frac{1}{2}
\left(\begin{array}{c|c} 
H_n & H_n\\
\hline
H_n & -H_n
 \end{array}\right)
\left(\begin{array}{c|c} 
R_{2^{n-1}} & 0\\
\hline
0 & I_{2^{n-1}}
 \end{array}\right)
\left(\begin{array}{c|c} 
H_n & H_n\\
\hline
H_n & -H_n
 \end{array}\right),
$$
Using the induction step, this product equals
$$-\frac{1}{2}\left(\begin{array}{c|c} 
-D_{2^{n-1}} + H_n^2 & -D_{2^{n-1}} - H_n^2\\
\hline
-D_{2^{n-1}} - H_n^2 & -D_{2^{n-1}} + H_n^2
 \end{array}\right) =
-\frac{1}{2}\left(\begin{array}{c|c} 
-D_{2^{n-1}} + I & -D_{2^{n-1}} - I\\
\hline
-D_{2^{n-1}} - I & -D_{2^{n-1}} + I
 \end{array}\right) = D_{2^n}, $$
where the equality $H_n^2=I$ comes from the fact that $H_n$ is symmetric. The last equality is checked easily by computing the diagonal and off-diagonal entries of the blocks.
