1
$\begingroup$

I have a sequence $a_0 = 1, a_1, a_2, a_3, \dots$ such that $a_4 = a_{24}$ which implies that period repeats after $a_{24}$ to $a_{43}$. Each $a_n$ depends on $a_{n-1}$ only. I need general term for this sequence for any value of $t$ whether $t < 4,\ t > 4,\ t$ can be as large as $10^{25}$.

There is another sequence such that $b_n = b_{n-1} + a_n$, how do I find the general term for this sequence $b$? Please note I am calculating all $a_n$ till the the cycle is found. I am very confused by this question? Currently I am getting answers close to the final answer but not exact ones? Please help.

PS: This is not a homeowork problem, its a algorithmic problem on spoj.

  • 0
    Can someone please provide a formal answer?2012-10-07

1 Answers 1

2

You have sequences $(a_n)$ and $(b_n)$ which satisfy recurrence relations $a_{n}=f(a_{n-1})$ with some function $f$ and $b_n=b_{n-1}+a_n.$ Moreover you found an index $k=4$ and a positive step size $d=20$ with $a_{k+d}=a_k$. It follows by induction that $a_{n+d}=a_n$ holds for all $n\ge k$. Therefore it is sufficient to calculate the values $a_1, a_2, \ldots, a_{k+d-1}$, the values $b_1,b_2, \ldots b_{k+d-1}$ and the "period sum" $s=a_k+a_{k+1}+\cdots + a_{k+d-1}.$ Then for $n\ge k+d$ we can write $n-k=q\cdot d+r$ with $q\in\mathbb N_0$ and $0\le r by division with remainder. With these $q,r$ we have $a_n = a_{k+r},$ $b_n = b_{k+r}+q\cdot s.$ The proof is easily done by induction.

(Of course, for $n, you simply lookup in your precomputed table of values).

  • 0
    :There seems to wrong for the exression for b [n] ?are you sure whether b[n] is correct for all cases? something looks wrong with it2012-10-08