1
$\begingroup$

How to find the $n$-th term in a sequence with following recurrence relation for a given $n$?

$$F(n)=2b F(n-1)-F(n-2), \ F(0)=a,\ F(1)=b,$$ where $a$ and $b$ are constants.

The value of $n$ is quite large $(1 \leq n\leq 10^{12})$ and so matrix exponentiation is required.

However I am facing difficulties deducing its matrix from the relation which would give the required value.

Could anyone help me with this question and show how to convert as well so I can tackle these kind of problems myself afterward?

$\endgroup$
10
  • $\begingroup$ The value of n is quite large ... and so matrix exponentiation is required Not clear on how matrix exponentiation helps there. One way or another, you'll get the same $\,F_n=c_1 u^n + c_2 v^n\,$ where $\,u, v\,$ are the roots of $\,x^2 - 2bx + 1 = 0\,$. It's easy to see that both roots are real, and they multiply to $\,1\,$, so one of them will be larger than $\,1\,$ in absolute value. That term will grow pretty quickly for large $\,n\,$, no matter how you calculate it. $\endgroup$
    – dxiv
    Commented Feb 9, 2018 at 23:53
  • $\begingroup$ This is the final step of a programming problem . Obviously , it could be done in linear time ( albeit it times out for some cases ) but matrix exponentiation has logarithmic complexity and doesn't time out. $\endgroup$
    – jah
    Commented Feb 10, 2018 at 11:40
  • $\begingroup$ I wasn't suggesting doing it in linear time. Integer powers can be calculated in logarithmic time (see here for example), and this applies to both real numbers and matrices. $\endgroup$
    – dxiv
    Commented Feb 10, 2018 at 18:03
  • $\begingroup$ Yes i am aware of that and the roots will be real but not necessarily integral . I will have to use float (or double ) which can lose accuracy with higher power and yield incorrect results . $\endgroup$
    – jah
    Commented Feb 10, 2018 at 19:23
  • $\begingroup$ The exponents are integers, which is what matters for log time exponentaition. The roots are real, and are in fact the eigenvalues of the associated matrix, which you have to raise to the same $n^{th}$ power anyway. $\endgroup$
    – dxiv
    Commented Feb 10, 2018 at 19:27

2 Answers 2

5
$\begingroup$

$$\begin{bmatrix} F_{n+1}\\F_n\end{bmatrix} = \begin{bmatrix} 2b&-1\\1\end{bmatrix}\begin{bmatrix} F_n\\F_{n-1}\end{bmatrix}$$

$$A = PDP^{-1}\\ A^n = PD^nP^{-1}$$

$$\lambda^2 - 2b +1 = 0\\ \lambda = b\pm\sqrt {b^2 - 1}$$

$$A^n = \frac{1}{\lambda_1 - \lambda_2}\begin{bmatrix} 1&1\\\lambda_2&\lambda_1\end{bmatrix}\begin{bmatrix}\lambda_1^n\\&\lambda_2^n\end{bmatrix}\begin{bmatrix} \lambda_1&-1\\-\lambda_2&1\end{bmatrix}$$

$$A^n = \frac{1}{\lambda_1 - \lambda_2} \begin{bmatrix}\lambda_1^{n+1}-\lambda_2^{n+1}&-(\lambda_1^n-\lambda_2)\\(\lambda_1\lambda_2)(\lambda_1^{n}-\lambda_2^n)&-(\lambda_1\lambda_2)(\lambda_1^{n-1}-\lambda_2^{n-1})\end{bmatrix}$$

But $\lambda_1\lambda_2 = 1$,

$$A^n = \frac{1}{\lambda_1 - \lambda_2} \begin{bmatrix}\lambda_1^{n+1}-\lambda_2^{n+1}&-(\lambda_1^n-\lambda_2)\\(\lambda_1^{n}-\lambda_2^n)&-(\lambda_1^{n-1}-\lambda_2^{n-1})\end{bmatrix}$$

$$F_{n+1} = \frac {(\lambda_1^{n+1}-\lambda_2^{n+1})b-(\lambda_1^{n}-\lambda_2^{n})a}{\lambda_1-\lambda_2}$$

$\endgroup$
4
  • $\begingroup$ This is exactly what i applied but i did not get the answers right. :( $\endgroup$
    – jah
    Commented Feb 9, 2018 at 22:54
  • $\begingroup$ What does your diagonlization look like? $\endgroup$
    – Doug M
    Commented Feb 9, 2018 at 22:55
  • $\begingroup$ I don't remember much about diagonalization and eigenvalues now but I don't think it would change the required value . Unfortunately your formula gives square roots which can lose accuracy with higher powers . Still thank you for your help on the matrix , maybe their is a problem with my code . $\endgroup$
    – jah
    Commented Feb 10, 2018 at 11:56
  • $\begingroup$ Yes there are square roots, but that doesn't mean that you must loose accuracy. $\endgroup$
    – Doug M
    Commented Feb 12, 2018 at 17:10
1
$\begingroup$

You might note that the generating function is $$g(x) = \frac{a + (1-2a)b x}{1 - 2 b x + x^2} = \frac{r(1-2a)b - a}{2(b - r) (x-r)} + \frac{s(1-2a)b - a}{(2(b-s)(x-s)}$$ where $x=r$ and $x=s$ are the roots of $1-2bx+x^2$ (assuming these are distinct), so that $$F(n) = \frac{(2a-1) b r - a}{2(r-b)} r^{-n-1} + \frac{(2a-1) b s - a}{2(s-b)} s^{-n-1}$$

$\endgroup$
1
  • $\begingroup$ I would like to know how you arrived at this but since i wouldn't understand it i won't ask :) . Unfortunately it involves square roots as well . An elegant solution , nonetheless . Upvoted . $\endgroup$
    – jah
    Commented Feb 10, 2018 at 12:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .