First off: you do not solve the Sherman-Morrison-Woodbury formula; the intention of this is to allow one to easily solve a set of linear equations when a rank-1 correction has been applied.
Secondly: it looks to me that you're not exploiting the occurrence of common subexpressions. It might aid you to see the computational savings you might accrue if you write SMW this way:
$$(\mathbf A+\mathbf u\mathbf v^T)^{-1}=\mathbf A^{-1}-\frac{\mathbf w(\mathbf A^{-1}\mathbf v)^T}{1-\mathbf v\cdot\mathbf w},\qquad \mathbf w=\mathbf A^{-1}\mathbf u$$
So let's see... assuming you have both the decomposed matrix and the inverse available (you do know that explicitly computing the inverse before multiplying to a vector can be unsound to do, yes?), you compute $\mathbf A^{-1}\mathbf u$ and $\mathbf A^{-1}\mathbf v$, take an outer and an inner product... well, you do the flop accounting. :)
I should preface this with a disclaimer. It may not be the kind of insight you are looking for and certainly not as insightful as the previous answers, but it is a very direct derivation only requiring the most basic knowledge of linear algebra.
Suppose you wish to solve the following for $\mathbf{x}$:
$$\left(A+\mathbf{uv}^T\right)\mathbf{x}=\mathbf{y}$$
$$A\mathbf{x}=\mathbf{y}-\mathbf{uv}^T\mathbf{x}$$
$$\mathbf{x}=A^{-1}\mathbf{y}-A^{-1}\mathbf{uv}^T\mathbf{x}$$
Notice that $\mathbf{v}^T\mathbf{x}$ is a scalar, let us call it $s$.
So the solution for $\mathbf{x}$ in terms of $s$ is:
$$\mathbf{x}=A^{-1}\mathbf{y}-A^{-1}\mathbf{u}s$$
And solving for $s$:
$$s=\mathbf{v}^T\mathbf{x}=\mathbf{v}^TA^{-1}\mathbf{y}-\mathbf{v}^TA^{-1}\mathbf{u}s$$
$$\left(1+\mathbf{v}^TA^{-1}\mathbf{u}\right)s=\mathbf{v}^TA^{-1}\mathbf{y}$$
$$s=\frac{\mathbf{v}^TA^{-1}\mathbf{y}}{1+\mathbf{v}^TA^{-1}\mathbf{u}}$$
Substituting for $s$ in the solution for $\mathbf{x}$:
$$\mathbf{x}=A^{-1}\mathbf{y}-\frac{A^{-1}\mathbf{uv}^TA^{-1}\mathbf{y}}{1+\mathbf{v}^TA^{-1}\mathbf{u}}$$
Or:
$$\mathbf{x}=\left(A^{-1}-\frac{A^{-1}\mathbf{uv}^TA^{-1}}{1+\mathbf{v}^TA^{-1}\mathbf{u}}\right)\mathbf{y}$$
So:
$$\left(A+\mathbf{uv}^T\right)^{-1}=A^{-1}-\frac{A^{-1}\mathbf{uv}^TA^{-1}}{1+\mathbf{v}^TA^{-1}\mathbf{u}}$$
Best Answer
Here's a proof adapted from wikipedia's proof for the (more general) Woodbury matrix identity.
We would like to find a matrix $X$ such that $$ (A + uv^T)X = I \implies AX + uv^TX = I $$ Now, if we define $Y = (v^TX)$, then we can rewrite this as a system of equations: $$ A X + uY = I\\ v^TX - Y = 0 $$ That is, $$ \pmatrix{A & u\\v^T&-1} \pmatrix{X\\Y} = \pmatrix{I\\0} $$ We can solve this system using an augmented matrix and block-matrix operations. In particular, we have $$ \left[ \begin{array}{cc|c} A & u & I\\ v^T & -1&0 \end{array} \right] \to \left[ \begin{array}{cc|c} I & A^{-1}u & A^{-1}\\ v^T & -1&0 \end{array} \right] \to \left[ \begin{array}{cc|c} I & A^{-1}u & A^{-1}\\ 0 & -1 - v^TA^{-1}u & -v^TA^{-1} \end{array} \right] \to\\ \left[\begin{array}{cc|c} I & A^{-1}u & A^{-1}\\ 0 & 1 & \frac{1}{1 + v^TA^{-1}u}v^TA^{-1} \end{array} \right] \implies \begin{cases} X + A^{-1}uY = A^{-1}\\ Y = \frac{1}{1 + v^TA^{-1}u}v^TA^{-1} \end{cases} $$ All that remains is substitution. That is, we have $$ X = A^{-1} - A^{-1}uY = A^{-1} - A^{-1}u\left( \frac{1}{1 + v^TA^{-1}u}v^TA^{-1}\right) = A^{-1} - \frac{A^{-1}uv^TA^{-1}}{1 + v^TA^{-1}u} $$