0
$\begingroup$

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.

3 Answers 3

1

$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
    +1. Though of course if $a-1$ is not coprime with $m$, then this formula is not so helpful.2012-06-28
1

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.

0

$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)$