I've almost got what I want. We start with $Ax = b $ and $(A + \Delta)\tilde{x} = b + \delta_b$. What I have then is
\begin{align*} \tilde{x} - x &= -A^{-1}\Delta\tilde{x} + A^{-1}\delta_b \\ \|\tilde{x} - x\| &\leq \|A^{-1}\|\left(\|\Delta\|\|\tilde{x}\| + \|\delta_b\|\right) \\ \frac{\|\tilde{x} - x\|}{\|x\|} &\leq \|A^{-1}\|\left(\|\Delta\|\frac{\|\tilde{x}\|}{\|x\|} + \frac{\|\delta_b\|}{\|x\|}\right) \end{align*} Now by $\|b\|\leq\|A\|\|x\|$ and $\frac{\|\tilde{x}\|}{\|x\|} \leq 1 + \frac{\|\tilde{x} - x\|}{\|x\|}$, we get \begin{align*} \frac{\|\tilde{x} - x\|}{\|x\|} &\leq \|A^{-1}\|\left(\|\Delta\|\left(1 + \frac{\|\tilde{x} - x\|}{\|x\|}\right) + \frac{\|\delta_b\|}{\|b\|}\|A\|\right)\\ &\leq \frac{\|\tilde{x} - x\|}{\|x\|}\|\Delta\|\|A^{-1}\| + \|A\|\|A^{-1}\|\left(\frac{\|\Delta\|}{\|A\|} + \frac{\|\delta_b\|}{\|b\|}\right) \end{align*} Taking the term on the rhs to the left and dividing gives \begin{align*} \frac{\|\tilde{x} - x\|}{\|x\|}&\leq \frac{\|A\|\|A^{-1}\|}{1 - \|\Delta\|\|A^{-1}\| }\left(\frac{\|\Delta\|}{\|A\|} + \frac{\|\delta_b\|}{\|b\|}\right). \end{align*}
The problem is, I want to show that \begin{align*} \frac{\|\tilde{x} - x\|}{\|x\|}&\leq \|A\|\|A^{-1}\|\left(\frac{\|\Delta\|}{\|A\|} + \frac{\|\delta_b\|}{\|b\|}\right), \end{align*} or in other words that $\|\Delta\|\|A^{-1}\| \leq 1$. The only bound I could find on the inverse is $1/\|A\| \leq \|A^{-1}\|$, which seems quite useless here. I'm not even sure if this is true, or if it is how do I show it. If not, where did I go wrong with my bounds? I'm really lost.