# Solving linear recurrence for large n

I came across this recurrence function:

$$F(n) = a \times F(n-1) + b$$

where $F(0) =1$. We have to solve for $F(n) \pmod {m}$

But for very large $n$, solving it with computer is also taking time. Is there anyway to simplify this. I think the values will be repeated again after some '$n$' based upon the values of $a,b$ and $m$. But I am unable to figure out how to solve it.

-

$F(n) = T(n) + c \implies T(n) + c = aT(n-1) + ac + b$.

Choosing $c = b/(1-a)$, we get that $T(n) = a T(n-1) \implies T(n) = a^n T(0)$.

Hence, $$F(n) = T(n) + c = a^n T(0) + b/(1-a) = a^n (F(0) - b/(1-a)) + b/(1-a)\\ \implies F(n) = a^n F(0) +b \dfrac{1-a^n}{1-a} = a^n + b \dfrac{1-a^n}{1-a}$$

If you are just interested in $F(n) \pmod{m}$, then make use of the recurrence. Call $G(n) = F(n) \pmod{m}$. Precompute $a' = a \pmod{m}$, $b' = b \pmod{m}$. Then we have that $$G(n) \equiv \left(a'G(n-1) + b' \right) \pmod{m}$$

-
+1. Though of course if $a-1$ is not coprime with $m$, then this formula is not so helpful. – Henning Makholm Jun 28 '12 at 19:31

If $m$ is small enough, compute when the sequence $$1,1+a,1+a+a^2,1+a+a^2+a^3,\dots\tag{1}$$ becomes $0\bmod{m}$. If the $k^{\text{th}}$ term of $(1)$ is $0\bmod{m}$, then $$\frac{a^k-1}{a-1}\equiv0\pmod{m}\quad\quad\text{and}\quad\quad a^k\equiv1\pmod{m}\tag{2}$$ Reduce $n'\equiv n\pmod{k}$ and you have $F(n)\equiv F(n')\pmod{m}$. If $m$ is much smaller than $n$, this will reduce the number of iterations.

If $m$ is large, then you can still compute (as shown by Marvis, et al) $$F(n)=a^nF(0)+b\frac{a^n-1}{a-1}\pmod{m}\tag{3}$$ Although $a^n$ and $\frac{a^n-1}{a-1}$ may get very big, $(3)$ takes very little time.

-

$F(n)=a.F(n-1)+b=a(a.F(n-2)+b)=a^2F(n-2)+ab=a^2(a.F((n-3)+b)+ab=a^3F(n-3)+a^2b+ab=\ldots=a^nF(0)+a^{n-1}b+\cdots +ab$

Now if $a\mod m\ne 1$ $$F(n)\mod m=(a\mod m)^n+(b\mod m)\frac{1-(a\mod m)^n}{1-a\mod m}$$

If $a\mod m=1$ then $a^i\mod m=1$ for all $i$, hence $F(n)\mod m=1+(n-1)(b\mod m)$

-