0
$\begingroup$

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?

  • 0
    Yes, I condensed notation incorrectly.2012-12-24

1 Answers 1

1

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, and somehow using this to show that $h(n)=g\big(n,h(n-1)\big)$.

  • 0
    @Alyosha: You’re welcome. (It sounds like you’ve got it, but it may help to think of it this way: you just want to show that $h$ and $f$ start in the same place and change in the same way from $n$ to $n+1$.)2012-12-24