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.

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.