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.

$\endgroup$
6
  • $\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$
    – hmakholm left over Monica
    Oct 7, 2012 at 10:22
  • $\begingroup$ @HenningMakholm:yes each a[n] depends on only a[n-1] $\endgroup$
    – user43255
    Oct 7, 2012 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, 2012 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$
    – hmakholm left over Monica
    Oct 7, 2012 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, 2012 at 10:45

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ :Is the period sum for my case,sum of a[4]+a[5]....+a[23]? $\endgroup$
    – user43255
    Oct 7, 2012 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, 2012 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, 2012 at 12:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .