From concrete mathematics problem 4.35 From Concrete Mathematics, problem 4.35.
Let $I(m,n)$ be function that satisfies the relation
$$I(m,n)m+I(n,m)n=\gcd(m,n)$$
when $m,n\in \Bbb N$ with $m\neq n$. Thus, $I(m,n)=m′$ and $I(n,m)=n′$ in (4.5). The value of $I(m,n)$ is an inverse of $m$ with respect to $n$. 

Find a recurrence that defines $I(m,n)$.

The (4.5) is just $m′m+n′n=\gcd(m,n)$.
I have no idea what I should do to solve the problem. What could I do with the condition "The value of $I(m,n)$ is an inverse of $m$ with respect to $n$".
Is it useful to get the result? 
 A: $$I(m,n)m+I(n,m)n=\gcd(m,n)\qquad\qquad(*)$$
By the symmetry of this equation we can assume WLOG that $m\lt n$.
To find the recurrence relation for $I$, we can use the logic that follows equation (4.5) in the text (Knuth, "Concrete Mathematics").
If $m=0$ then we can have $I(0,n)=0$ and $I(n,0)=1$ to satisfy $(*)$ since $\gcd(0,n)=n$.
So assume now that $m\gt 0$. Letting $m_1=n-\left\lfloor\frac{n}{m}\right\rfloor m\;$ and $\;n_1=m,\;$ we have $\;m_1 \lt n_1$ and $m_1,n_1\in\mathbb{N}$. Therefore, function $I$ must satisfy:
\begin{eqnarray*}
I(m_1,n_1)m_1 + I(n_1,m_1)n_1 &=& \gcd(m_1,n_1) \\
&& \\
\therefore\quad I(m_1,n_1)\left(n-\left\lfloor\frac{n}{m}\right\rfloor m\right) + I(n_1,m_1)m &=& \gcd(m,n) \\
&& \\
\therefore\quad \left(I(n_1,m_1) - \left\lfloor\frac{n}{m}\right\rfloor I(m_1,n_1)\right)m + I(m_1,n_1)n &=& \gcd(m,n).
\end{eqnarray*}
Comparing this with $(*)$ we see that:
\begin{eqnarray*}
I(m,n) &=& I(n_1,m_1) - \left\lfloor\frac{n}{m}\right\rfloor I(m_1,n_1) \qquad\text{and} \\
I(n,m) &=& I(m_1,n_1).
\end{eqnarray*}
So our recurrence relation for $I$, with $m\lt n$ is:
\begin{eqnarray*}
I(0,n) &=& 0 \\
I(n,0) &=& 1 \\
I(m,n) &=& I(m,n-\left\lfloor\frac{n}{m}\right\rfloor m) - \left\lfloor\frac{n}{m}\right\rfloor I(n-\left\lfloor\frac{n}{m}\right\rfloor m,m) \\
I(n,m) &=& I(n-\left\lfloor\frac{n}{m}\right\rfloor m,m).
\end{eqnarray*}
$$\\$$
$$\\$$
We illustrate using the example from the text, where $m=12, n=18$:
\begin{eqnarray*}
I(12,18) &=& I(12, 18 - \left\lfloor\frac{18}{12}\right\rfloor 12) - \left\lfloor\frac{18}{12}\right\rfloor I(18 - \left\lfloor\frac{18}{12}\right\rfloor 12, 12) \\
&& \\
&=& I(12,6) - I(6,12) \\
&& \\
&=& \left[I(12- \left\lfloor\frac{12}{6}\right\rfloor 6,6)\right] - \left[I(6,12 - \left\lfloor\frac{12}{6}\right\rfloor  6) - \left\lfloor\frac{12}{6}\right\rfloor  I(12 - \left\lfloor\frac{12}{6}\right\rfloor 6,6)\right] \\
&& \\
&=& I(0,6) - I(6,0) + 2I(0,6) \\
&& \\
&=& 0-1 + 2\times 0 = -1. \\
&& \\
I(18,12) &=& I(18 - \left\lfloor\frac{18}{12}\right\rfloor 12, 12) \\
&& \\
&=& I(6,12) \\
&& \\
&=& I(6, 12 - \left\lfloor\frac{12}{6}\right\rfloor 6) - \left\lfloor\frac{12}{6}\right\rfloor I(12 - \left\lfloor\frac{12}{6}\right\rfloor 6, 6) \\
&& \\
&=& I(6,0) - 2I(0,6) \\
&& \\
&=& 1-2\times 0 = 1.
&& \\
&& \\
\text{So we have} && -1\times m + 1\times n = \gcd(m,n) \\
&& \\
\text{i.e.} && -1\times 12 + 1\times 18 = 6. \qquad\checkmark
\end{eqnarray*}
Note: The text's remark about the inverse, I honestly can't make sense of that. But it doesn't seem necessary to the question anyway.
