# Can a recurrence relation be translated to a composite function of itself?

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.

• I wonder why you need that; $n$-fold composition seems unnatural compared to recursion. Are you studying fixed-point theory? – Raphael Mar 23 '13 at 16:19
• No, I am studying composition, but I'll probably find fixed point theory on the road.. – Hernan_eche Apr 10 '13 at 17:26

 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?

• what is return (1,1) ? it should return float? I am confused – Hernan_eche Apr 10 '13 at 17:22
• @Hernan_e, it's the pair 1 1 not a float – wece Apr 11 '13 at 20:52

If I understand your question correctly, the function

$\qquad f(x) = \langle \frac{1}{2} \cdot (3x[1] - 2x[2]) , x[1] \rangle$,

with $\langle \cdot \rangle : \mathbb{N}^2 \to \mathbb{N}$ an encoding of tuples so that $a = \langle b, c \rangle \iff a[1] = b \land a[2] = c$, does the job in the sense that

$\qquad (\underbrace{f \circ \dots \circ f}_{n-1 \text{ times}})(\langle 1,1\rangle)[1] = a_n$

for $n \geq 2$. As implementation of $\langle \cdot \rangle$, you can use for instance Cantor's pairing method.

Note how above idea generalises easily: for a recurrence of degree $k$

$\qquad a_n = g(a_{n-1},\dots,a_{n-k}) + h(n)$,

use

$\qquad f(x) = \langle g(x[1], \dots, x[k]) , x[1], \dots, x[k-1] \rangle$.

• It seems to be an answer, but I still cant translate it to a source code, I mean recursive programming function.. I can't understand what x[1] and x[2] are. – Hernan_eche Apr 10 '13 at 17:23
• @Hernan_e I defined it in the third line; it denotes the inverse of the tuple encoding. – Raphael Apr 10 '13 at 18:11