How can I find the general form of a recursive formula?

[dyh]

Hey guys,

I would like to get some general form of recursive formula

let f(s) = (a+bs)/(c+ds)

given this I would like to get nth composite function of f

i.e the general form of f^n(s)= fofofofofo...of(s) (nth composite)

I can conjecture that the form of f^n(s) would be the same form with f(s) like

f^n(s) = (α+βs)/(γ+δs)

and α,β,γ,δ are would be expressed as function of a,b,c,d and n

So, I would like to get the general from of α,β,γ,δ with the function of a,b,c,d and n.

Thanks

 

[Mute]

Your function is called a Mobius transformation. By looking up references about this function you may be able to find some information about the composition of functions that you want to find. A brief skim of the wikipedia article didn't yield a discussion of composition of the function, but I did see a section about fixed points of the transformation, which is related to composing the function infinitely many times.

 

[jasonRF]

dyh,

Your conjecture is correct. The solution ends up consisting of matrix multiplies. For example, if
$$z_1 = \frac{a z + b}{c z + d}$$
and
$$z_2 = \frac{a_1 z_1 + b_1}{c_1 z_1 + d_1}$$
then if we want to write
$$z_2 = \frac{a_2 z + b_2}{c_2 z + d_2}$$
we have
$$\left( \begin{array}[cc] \\ a_2 & b_2 \\ c_2 & d_2 \end{array} \right)<br /> =<br /> \left( \begin{array}[cc] \\ a_1 & b_1 \\ c_1 & d_1 \end{array} \right)<br /> \left( \begin{array}[cc] \\ a & b \\ c & d \end{array} \right) .$$

You should work through the algebra yourself to verify that I didn't make a mistake. Composition of more than two of these leads to simply more matrices to multiply. In your case, $a_1=a, b_1=b,$ etc. so you would simply have an nth power of a matrix. If your matrix can be diagonalized then this nth power is relatively simple.

By the way, this functional form is often called a Mobius (or bilinear) transformation. If you have ever learned about conformal mapping, you may recall that it maps circles/lines in the complex plane to other circles/lines.

jason

 

[dyh]

Thanks buddy! It is really helpful.
I will try to get the specific form!