[Solved]: Can a recurrence relation be translated to a composite function of itself?

Problem Detail: 

Perhaps this is a question for stackoverflow because its practical nature, but I am not aware of any general method to relate recurrence relations and recursive functions.

Having as an example this recurrence relation:

$\qquad \begin{align}a_0 &= a_1 = 1 \\ 2a_n &= 3a_{n-1}-2a_{n-2}\end{align}$

I would like to transform it into a recursive function $f$, able to be called to itself a number of times (composite), i.e. $f \circ f \circ f \circ \dots \circ f$ ($n$ times), getting the same result as with the $a_n$ relation.

Any ideas about it?

Asked By : Hernan_eche

Answered By : wece

 static float f(int n,int m)       {          if((n==1)||(m==0)) return (1,1);          return ((3*n - 2*m)/2,n);       } 

That way $\underbrace{f\circ f\circ \dots \circ f}_{\text{n times}} (1,0)=(a_n,a_{n-1})$.

Is that what you wanted?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10706

3.2K people like this

 Download Related Notes/Documents