You are given that $f(n)=g(n, f(n-1))$ (some initial values given). Looking at the first few terms, it becomes obvious that $f(n)=h(n)$. How does one go about proving this?
Induction seemed obvious at first, but I found it hard applying induction to this type of problem (with recursive functions, so difficult to rearrange):
Hypothesis:$h(n)=g(n, f(n-1))$
Show that $h(t, f(t))=g(n, f(n-1))$ implies both
$(1)$ $g(1, f(1-1))=h(1),$ and
$(2)$ $h(n+1, f(n+1))=g(n+1, f(n-1+1))$?
I don't think $(2)$ is correct, as by the same logic you could prove $n^2=n^3$ by the fact that$(1)^2=(1)^3$ and that $n^2=n^3$ implies $(n+1)^2=(n+1)^3$. How is $(2)$ really done?
Is there another method besides induction more suited to this problem?
I’m going to assume that you meant that $f(n)=g\big(n,f(n-1)\big)$, as what you wrote attempts to define $f(n)$ in terms of itself.
What you need to do is show that $h$ satisfies the same initial conditions and recurrence as $f$. Presumably verifying that $h$ and $f$ satisfy the same initial conditions is not a problem. You have some $n_0$ such that $f$ satisfies the recurrence $f(n)=g\big(n,f(n-1)\big)$ for all $n\ge n_0$, so you must show that $h(n)=g\big(n,h(n-1)\big)$ for $n\ge n_0$. Your induction step will consist in letting $n>n_0$ be arbitrary, assuming as your induction hypothesis that $h(k)=g\big(k,h(k-1)\big)$ for $n_0\le k<n$, and somehow using this to show that $h(n)=g\big(n,h(n-1)\big)$.