= Sum of an eventually periodic sequence
{title2=$\sum_{j=0}^{L-1}u_{N+j}=qC+\sum_{j=0}^{r-1}u_{N+j},\quad L=qT+r$}
Suppose a numerical <sequence> has period $T$ from index $N$, and let $C=\sum_{j=0}^{T-1}u_{N+j}$. For $L=qT+r$ with $0\leq r<T$, split the required <sum> into $q$ complete periods and a tail of length $r$. Every complete period contributes $C$, proving the formula in the title. Precomputed <prefix sums> of one period make the tail lookup constant time. If this periodic <sequence> consists of the <first differences> of another <sequence>, the same formula extrapolates that original <sequence> by adding the initial value at $N$.
Back to article page
