Conjugate gradient - gradients orthogonality proof I need to prove that $\left<r_{k+1}, r_k\right> = 0$ ($r_{k} = \nabla f(x_k)$)
in the conjugate gradient method for quadratic functions.
We can use the property of quadratic functions:
$$ r_{k+1} = r_{k} - \alpha_{k} A d_{k} $$
and multiply it by $r_{k}$:
$$
\left<r_{k+1}, r_k\right> = \left\lVert{r_{k}}\right\lVert^2 - \alpha_{k} \left< A d_{k},
  r_{k} \right>
$$ 
$\alpha_{k}$ is chosen to be locally optimal ($f(x_{k} - \alpha_{k} d_{k}) \to \min$):
$$
f(x_{k} - \alpha_{k} d_{k}) = f(x_{k}) - \alpha_{k} \left< r_{k}, d_{k}\right> +
\frac{1}{2}\alpha_{k}^{2} \left< A d_{k}, d_{k}\right>
$$
$$
\frac{\partial{f}}{\partial{\alpha_k}} = - \left< r_{k}, d_{k}\right> +
\alpha_{k} \left< A d_{k}, d_{k}\right> = 0
$$
$$
\alpha_{k} = \frac{\left< r_{k}, d_{k}\right>}{\left< A d_{k}, d_{k}\right>}
$$
on substituting:
$$
\left<r_{k+1}, r_k\right> = \left\lVert{r_{k}}\right\lVert^{2} - \frac{\left< r_{k}, d_{k}\right>}{\left< A d_{k}, d_{k}\right>} \left< A d_{k},
  r_{k} \right>
$$ 
I'm stuck here. How can we simplify it and get $\frac{\left< r_{k}, d_{k}\right>}{\left< A d_{k}, d_{k}\right>} \left< A d_{k},
  r_{k} \right> = \left\lVert{r_{k}}\right\lVert^{2}$?
 A: I am aware of the following proof using various properties of the CG method - there might be one out there with less required properties. For another question I outlined the derivation of the method and will re-use results here.
The sort of defining property of the CG iterates $\boldsymbol x^k$ is that they are optimal with respect to the space spanned by the update directions $\boldsymbol p^j$:
$$ \big \langle \underbrace{A \boldsymbol x^k - \boldsymbol b}_{=: \boldsymbol r^k}, \boldsymbol p^j \big \rangle = 0, \quad j = 0, \dots, k-1$$
Another useful property of CG is that the space spanned by the update directions $V_k := \text{span} \Big \{ \boldsymbol p^0 , \dots \boldsymbol p^{k-1} \Big \}$ equals the space spanned by the residuals: $V_k = R_k := \text{span} \Big \{ \boldsymbol r^0 , \dots \boldsymbol r^{k-1} \Big \}$. As a consquence,
$$ \big \langle \boldsymbol r^{k+1}, \boldsymbol p^j \big \rangle = 0, \quad j = 0, \dots, k \Leftrightarrow \big \langle \boldsymbol r^{k+1}, \boldsymbol r^j \big \rangle = 0, \quad j = 0, \dots, k$$
which implies also in particular
$$\big \langle \boldsymbol r^{k+1}, \boldsymbol r^k \big \rangle = 0.$$
