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.

I was trying to simplify the following sequence, such that I can calculate the $n$th term in $\log n$ time. This can be done, if we can express the $n$th in terms of combinations of Fibonacci like numbers.

$$S_{n} = (S_{n-1} * S_{n-2} )^k$$ given that $S_{0} = a$, $S_{1} = b$ and $k$ is an fixed integer.

I tried my best but could not find a simple formula. Is it possible to get some simple generating function so that I can convert that to Matrix form for calculating in $S_{n}$ in $\log n$ time.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

Take logarithms, and define $T_n = \log S_n$. Then the recurrence relation $S_n = (S_{n-1} S_{n-2})^k$ becomes $$\log S_n = k(\log S_{n-1} + \log S_{n-2})$$ $$T_n = kT_{n-1} + kT_{n-2}$$

Now you can find $T_n$ in time $O(\log n)$, and then get back $S_n$ as $S_n = b^{T_n}$, where $b$ is the base of your logarithms.


Just to elaborate: To find $T_n$ in time $O(\log n)$, we can do the following. Let the matrix $A = \begin{pmatrix}0 & 1 \\ k & k \end{pmatrix}$, and the vector $X_n = \begin{pmatrix}T_n \\ T_{n+1}\end{pmatrix}$. Note that $X_n = AX_{n-1}$, and therefore $X_n = A^n X_0$. Now you can find $A^n$ in time $O(\log n)$ using the usual exponentiation-by-repeated-squaring trick, and you know $X_0 = \begin{pmatrix}T_0 \\ T_1\end{pmatrix}$, so you can calculate $X_n$.

share|improve this answer
    
Nice one! I will try that. I guess we can just use 2*2 matrix exponentiation. –  sabari Sep 13 '12 at 13:05
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.