Summation Chains of Sequences Part 1: Introduction, Generation, and Key Definitions

Summation Chains of Sequences Part 1: Introduction, Generation, and Key Definitions

For the full paper, which includes all proofs, download the pdf here

Summation Chains of Sequences

Key Definition and Formulas

Let M be a set, and let X be the set of sequences of elements in M. Given a function rule f on X, and an f-chain, c, in order to keep notation clean, new notation is defined as follows. c(m,n) := the nth term of the sequence c(m).

Using this notation we give a clean definition of a summation chain of sequences.

Definition. Let M be a \mathbb{Z}-Module. A summation chain, denoted \Sigma-chain, of is a function c:\mathbb{Z} \times \mathbb{N} \to M where c(m,n)=\sum_{k=1}^{n} c(m-1,k), for all m\in \mathbb{Z} and for all n\in \mathbb{N}\Phi_{\Sigma[M]} is the seed mapping for summation chains in M. The notation \Phi_{\Sigma} is used when the \mathbb{Z}-Module, M, is clear. \mathcal{C}_{\Sigma[M]} denotes the set of all M-valued summation chains.

Remark. Summation chains are generated by the function rule T_{\Sigma}:M^{\infty}\to M^{\infty} where T_{\Sigma}(x_1,x_2,x_3,\ldots)=(x_1,x_1+x_2,x_1+x_2+x_3,\ldots).

Example. Let t:\mathbb{Z}\times \mathbb{N} \to M be the constant function t(m,n)=0.

\sum_{k=1}^{n} t(m-1,k) =\sum_{k=1}^{n} 0 =0=t(m,n),

so t is a \Sigma-chain. This chain is the trivial chain and is generated with the sequence of all zeros.

How can the sequences in a summation chain be computed quickly? The next two results provide ways to compute entries of a summation chain. The next proposition provides a way to compute the entries in a chain using the other entries close to it.


Let M be a \mathbb{Z}-Module. Let c:\mathbb{Z} \times \mathbb{N} \to M be a function. c is a \Sigma-chain in M if and only if for all m,m' \in \mathbb{Z} and n \in \mathbb{N}, the following equalities hold.

  1. c(m,1)=c(m',1),
  2. If n \geq 2, then

The next theorem provides a way to calculate any sequence in a summation chain directly given any other sequence in the chain without having to compute any of the sequences in between.


Let natural numbers, n and k, where k < n.
{n \choose k}={n-1 \choose k-1}{n-1 \choose k}



Let c be a \Sigma-chain in \mathbb{Z}-Module M. Let m_1,m_2 \in \mathbb{Z} such that m_1>m_2, and let n\in \mathbb{N}. Define m=m_1-m_2.
c(m_1,n)=\sum_{k=1}^{n} {m+n-k-1 \choose m-1} c(m_2,k)

If n\geq m+1,

c(m_2,n)= \sum_{k=0}^{m} (-1)^{m-k}{m \choose m-k} c(m_1,n-m+k).

If n\leq m+1,

c(m_2,n)=\sum_{k=1}^{n} (-1)^{n-k}{m \choose n-k} c(m_1,k).

Remark.When n=m+1, the two equations above are the same.

Example. Let c=\Phi_{\Sigma[\mathbb{R}]}((2^{k-1})). The following is a computation of the sequences c(-5,n) and c(-6,n).


When n\geq 6,

\begin{aligned}c(-5,n)&=\sum_{i=0}^4{4 \choose i}c(0,n-i)\\&=c(0,n)-5c(0,n-1)+10c(0,n-2)\\&\kern{3em}-10c(0,n-3)+5c(0,n-4)-c(0,n-5)\\&=2^{n-1}-5\cdot 2^{n-2}+10\cdot 2^{n-3}-10\cdot 2^{n-4}+5\cdot 2^{n-5}-2^{n-6}\\&=2^{n-6}(32-5\cdot 16+10\cdot 6-10\cdot 4+5\cdot 2-1)\\&=2^{n-6}(1)\\&=2^{n-6}\end{aligned}


When n\geq 7, c(-6,n)=c(-5,n)-c(-5,n-1)=2^{n-6}-2^{n-7}=2^{n-7}

Example. Let a_1=1, a_2=-1, and a_k=0 when k\geq 3. Let c=\Phi_{\Sigma[\mathbb{R}]}((a_k)). The following is a computation of the sequence c(4,n).


When n\geq 2,
\begin{aligned}c(4,n)&=\sum^{n}_{k=1}{3+n-k \choose 3}c(0,k)\\&={n+2 \choose 3}-{n+1 \choose 3}\\&=\frac{n(n+1)(n+2)}{6}-\frac{(n-1)n(n+1)}{6}\\&=\frac{n(n+1)[(n+2)-(n-1)]}{6}\\&=\frac{n(n+1)}{2}\\\end{aligned}