Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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

Your Answer


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.