Compute $\sum_0^{n-1}2^i11^{n-i-1}\bmod10^9$ when $n=13^{17}$

Question

Given the following function $f$
$f(1)=1$
$f(n)=11\cdot f(n-1)+2^{n-1}$

I would like to compute $f(13^{17})\mod 10^9$ and ended up using the following :

$f(n)=\sum_{i=0}^{n-1}({11^{n-(i+1)}\cdot 2^i})$

though I am able to quickly compute a single term using modular exponentiation, the loop over $13^{17}-1$ takes ages.

So do you have any suggestion to simplify $f(n)$ to avoid the loop ?

Answer 1

Note that $f(n)$ may be simply rewritten as $\displaystyle f(n)=\frac{11^n-2^n}{11-2}$

Answer 2

Clearly $f(n)$ will be of the form $a \cdot 11^n+b \cdot 2^n$ where $a,b$ are integers. Given $f(1)=1$, but $f(1)=11a+2b$. Similarly $f(2)=11f(1)+2=13$, but $f(2)=121a+4b$.

Solving for $a,b$, we get $f(n)= \frac{11^n-2^n}9$.

$f(13^{17})=\frac{11^{13^{17}}-2^{13^{17}}}9$.

$11^{13^{17}} = (10+1)^{13^{17}}=1+{13^{17}} \cdot 10^{13^{17}} + \dots \equiv 1 \pmod {10^{13^{17}}} \equiv 1 \pmod{10^9}$

Let $2^{13^{17}} \equiv c \pmod{10^9} = k10^9+c$

Clearly,$\left(2^{13^{17}},\ 10^9\right)\bigg|c \Rightarrow c$ is of the form $2^9d \Rightarrow 2^{13^{17}-9} \equiv d \pmod{2^9}$

As $2$ is a primitive root of $5$ and of $5^2$ ,s o it'll be of $5^n$, $n \geq 1$. $\phi(5^9)=4 \cdot 5^8$.

So, taking discrete logarithm in base $2$, ${13^{17}-9} \equiv \operatorname{ind}_2d \pmod{4 \cdot 5^8}$ =>$\operatorname{ind}_2d\equiv{(13^{17}-9)}\pmod {4 \cdot5^8}$.

and so on.