[proofplan] We prove by induction on $k$ that $r^{(k)}$ is orthogonal to $\operatorname{span}\{d^{(0)}, \ldots, d^{(k-1)}\}$, using the [Error Projection Along Search Direction](/theorems/1398) theorem as the key tool. The base case $k = 1$ follows directly from that theorem. The inductive step combines the inductive hypothesis ($e^{(k)}$ is $A$-orthogonal to $d^{(0)}, \ldots, d^{(k-1)}$) with the conjugacy of the directions ($\langle d^{(k)}, d^{(j)} \rangle_A = 0$ for $j < k$) to show $\langle e^{(k+1)}, d^{(j)} \rangle_A = 0$ for all $j \leq k$. After $n$ steps, $e^{(n)}$ is $A$-orthogonal to all $n$ conjugate directions, which span $\mathbb{R}^n$, forcing $e^{(n)} = 0$. [/proofplan] [step:Verify that pairwise conjugate directions form a basis of $\mathbb{R}^n$] The directions $d^{(0)}, \ldots, d^{(n-1)}$ are pairwise conjugate with respect to $A$: $\langle d^{(i)}, d^{(j)} \rangle_A = 0$ for $i \neq j$. Since $A$ is positive definite, $\langle \cdot, \cdot \rangle_A$ is an inner product on $\mathbb{R}^n$. A set of $n$ mutually orthogonal nonzero vectors in an $n$-dimensional inner product space is linearly independent (if $\sum_i c_i d^{(i)} = 0$, then taking $\langle \cdot, d^{(j)} \rangle_A$ gives $c_j \langle d^{(j)}, d^{(j)} \rangle_A = 0$, hence $c_j = 0$). Therefore $\{d^{(0)}, \ldots, d^{(n-1)}\}$ is a basis of $\mathbb{R}^n$. [/step] [step:Prove by induction that $\langle e^{(k)}, d^{(j)} \rangle_A = 0$ for all $j < k$] **Base case ($k = 1$).** By the [Error Projection Along Search Direction](/theorems/1398), $\langle e^{(1)}, d^{(0)} \rangle_A = 0$. Since $\langle r^{(1)}, d^{(0)} \rangle = \langle Ae^{(1)}, d^{(0)} \rangle = \langle e^{(1)}, d^{(0)} \rangle_A = 0$, the residual $r^{(1)}$ is orthogonal to $d^{(0)}$. **Inductive step.** Assume $\langle e^{(k)}, d^{(j)} \rangle_A = 0$ for all $j = 0, \ldots, k-1$. The error recurrence from the [Error Projection Along Search Direction](/theorems/1398) gives: \begin{align*} e^{(k+1)} = e^{(k)} - \frac{\langle e^{(k)}, d^{(k)} \rangle_A}{\langle d^{(k)}, d^{(k)} \rangle_A}\,d^{(k)}. \end{align*} For $j < k$, take the $A$-inner product with $d^{(j)}$: \begin{align*} \langle e^{(k+1)}, d^{(j)} \rangle_A = \underbrace{\langle e^{(k)}, d^{(j)} \rangle_A}_{= 0 \text{ (inductive hypothesis)}} - \frac{\langle e^{(k)}, d^{(k)} \rangle_A}{\langle d^{(k)}, d^{(k)} \rangle_A}\underbrace{\langle d^{(k)}, d^{(j)} \rangle_A}_{= 0 \text{ (conjugacy, } j \neq k)} = 0. \end{align*} For $j = k$, the [Error Projection Along Search Direction](/theorems/1398) directly gives $\langle e^{(k+1)}, d^{(k)} \rangle_A = 0$. Therefore $\langle e^{(k+1)}, d^{(j)} \rangle_A = 0$ for all $j = 0, \ldots, k$, completing the induction. [guided] The inductive step uses two distinct orthogonality properties: 1. **The inductive hypothesis:** $\langle e^{(k)}, d^{(j)} \rangle_A = 0$ for $j < k$. This says that the error at step $k$ has already been made $A$-orthogonal to all previous search directions. 2. **Conjugacy of the directions:** $\langle d^{(k)}, d^{(j)} \rangle_A = 0$ for $j \neq k$. This is the structural assumption on the search directions. When we expand $\langle e^{(k+1)}, d^{(j)} \rangle_A$ for $j < k$, the first term vanishes by (1) and the second by (2). For $j = k$, we use the Error Projection theorem directly. The critical question is: why does the new step (along $d^{(k)}$) not destroy the $A$-orthogonality to previous directions? The answer is exactly conjugacy: since $d^{(k)}$ is $A$-orthogonal to $d^{(0)}, \ldots, d^{(k-1)}$, adding a multiple of $d^{(k)}$ to $e^{(k)}$ does not change the $A$-inner product with any previous direction. Since $\langle r^{(k)}, d^{(j)} \rangle = \langle Ae^{(k)}, d^{(j)} \rangle = \langle e^{(k)}, d^{(j)} \rangle_A$, the statement "$r^{(k)}$ is orthogonal to $\operatorname{span}\{d^{(0)}, \ldots, d^{(k-1)}\}$" is equivalent to "$e^{(k)}$ is $A$-orthogonal to $\operatorname{span}\{d^{(0)}, \ldots, d^{(k-1)}\}$". [/guided] [/step] [step:Conclude that $r^{(n)} = 0$ from $A$-orthogonality to a basis] After $n$ steps, the induction gives $\langle e^{(n)}, d^{(j)} \rangle_A = 0$ for all $j = 0, \ldots, n-1$. Since $\{d^{(0)}, \ldots, d^{(n-1)}\}$ is a basis of $\mathbb{R}^n$ (established in the first step), the vector $e^{(n)}$ is $A$-orthogonal to every vector in $\mathbb{R}^n$. In particular, $\langle e^{(n)}, e^{(n)} \rangle_A = 0$. Since $A$ is positive definite, $\langle v, v \rangle_A = 0$ implies $v = 0$. Therefore $e^{(n)} = 0$, which means $x^{(n)} = x^*$, and consequently $r^{(n)} = Ae^{(n)} = 0$. [/step]