Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Do you mean that $f(n)=g(n,f(n-1))$? –  Brian M. Scott Dec 24 '12 at 12:50
    
Yes, I condensed notation incorrectly. –  Alyosha Dec 24 '12 at 12:56
add comment

1 Answer

up vote 1 down vote accepted

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)$.

share|improve this answer
    
Thanks- I was going the wrong way, trying to force $h(n)$ out of $g(n,f(n-1))$. –  Alyosha Dec 24 '12 at 12:59
    
@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$.) –  Brian M. Scott Dec 24 '12 at 13:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.