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

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

## 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}