# Derive a General formula for each term of this periodic sequence?

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.

• $a_{4}=a_{24}$ does not imply that the sequence repeats after $a_{24}$, unless you have some additional information that you haven't told us (such as, for example, that each $a_n$ depends only on $a_{n-1}$). Oct 7, 2012 at 10:22
• @HenningMakholm:yes each a[n] depends on only a[n-1] Oct 7, 2012 at 10:24
• @HenningMakholm:can't it be done by just finding the period and all terms upto the period Oct 7, 2012 at 10:36
• Yes, with that additional information it is enough to find the terms up to the repeat, and then take the remainder of each higher index modulo 20. Oct 7, 2012 at 10:38
• @HenningMakholm:But what about sequence B? What will be the general term for it ? also we need a correction as period starts from 4 not 1 Oct 7, 2012 at 10:45

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<d$ 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<k+d$, you simply lookup in your precomputed table of values).
• Yes, the sum over a complete period (without any pre-period terms). As your example has $k=4$ and $d=20$, the sum should run from $a_k=a_4$ to $a_{k+d-1}=a_{23}$. Oct 7, 2012 at 11:18