The functions f : N → N and g : N^2 → N are recursively defined as follows:
f(0) = 1
f(n) = g(f(n − 1), 2n) if n ≥ 1
g(0, n) = 0 if n ≥ 0
g(m, n) = g(m − 1, n) + n if m ≥ 1 and n ≥ 0.
After a proof by induction on $m$, the recurrence for $g$ is supposed to be proven to be $g(m, n) = mn$
I am not sure where to get the assumption that $g(m, n) = mn$ based off of the above information.
On
Here is a derivation of $g(m,n) = mn$. We do this by eliminating the explicit $n$ from the recursion formula for $g$. Thus,
$$ g_{m,n}=g_{m−1,n}+n\\ g_{m-1,n}=g_{m−2,n}+n\\ $$
Subtract to get
$$g_{m,n}=2g_{m-1,n}-g_{m-1,n}$$
The characteristic roots of this equation are
$$\alpha,\beta=\frac{2\pm\sqrt{2^2+4\cdot (-1)}}{2}=1,1$$
When these root are the same, the general formula takes the form
$$ f_n=af_{n-1}+bf_{n-2}\\ \alpha,\beta=\frac{a\pm\sqrt{a^2+4b}}{2}\\ {{f}_{n}}=\left[ n{{f}_{1}}-(n-1)\frac{a{{f}_{0}}}{2} \right]\,{{\alpha }^{n-1}},\quad \alpha=\beta $$
In the present case, with $g_{0,n}=0$ and $g_{1,n}=n$, this becomes
$$g_{m,n}=mn$$
We have $g(m,n) =mn,$ thus $f(n) =g(f(n-1) , 2n) =2nf(n-1)$ hence $f(n) =2^n n!.$