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}$). – Henning Makholm Oct 7 '12 at 10:22
• @HenningMakholm:yes each a[n] depends on only a[n-1] – user43255 Oct 7 '12 at 10:24
• @HenningMakholm:can't it be done by just finding the period and all terms upto the period – user43255 Oct 7 '12 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. – Henning Makholm Oct 7 '12 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 – user43255 Oct 7 '12 at 10:45

1 Answer

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

• :Is the period sum for my case,sum of a[4]+a[5]....+a[23]? – user43255 Oct 7 '12 at 11:18
• 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}$. – Hagen von Eitzen Oct 7 '12 at 11:18
• :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 it – user43255 Oct 8 '12 at 12:04