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.

Proposition.

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
    c(m,n)=c(m,n-1)+c(m-1,n)=c(m+1,n)-c(m+1,n-1).

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.

Lemma.

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

 

Theorem.

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

c(-5,1)=c(0,1)=1.
c(-5,2)=c(0,2)-5c(0,1)=2-5(1)=-3.
c(-5,3)=c(0,3)-5c(0,2)+10c(0,1)=4-5(2)+10(1)=4.
c(-5,4)=c(0,4)-5c(0,3)+10c(0,2)-10c(0,1)=8-5(4)+10((2)-10(1)=-2.
c(-5,5)=c(0,5)-5c(0,4)+10c(0,3)-10c(0,2)+5c(0,1)=16-5(8)+10(4)-10((2)+5(1)=1.

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}

c(-6,1)=c(-5,1)=1
c(-6,2)=c(-5,2)-c(-5,1)=-3-1=-4
c(-6,3)=c(-5,3)-c(-5,2)=4-(-3)=7
c(-6,4)=c(-5,4)-c(-5,3)=-2-4=-6
c(-6,5)=c(-5,5)-c(-5,4)=1-(-2)=3
c(-6,6)=c(-5,6)-c(-5,5)=1-1=0

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

c(4,1)=c(0,1)=a_1=1

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}