# What's the rule for solving nested sums?

I have the following nested double sum :

$\sum_{t=1}^{T}\sum_{u=t}^{T} Z(u) \cdot (1+i)^{-u}$ with $0<i<1$ and $Z(u)$ being a non-specified function.

By working with an example of $T=3$ I suppose the solution should be

$\sum_{t=1}^T t \cdot Z(t) \cdot (1+i)^{-t}$.

Is that correct?

My problem is to figure out which calculation rule for sums is to apply here when you have the index of the outer sum as starting point for the second sum. The normal commutative and distributive rule don't seem to apply here. I can hardly argue "It works for $T=3$ so it must be right for all $T$." Could someone please tell me the general/universal calculation rule?

Does/how does the solution change when the sum is changed to

$\sum_{t=1}^{T}\sum_{u=t}^{T} Z(u) \cdot (1+i)^{-u+t}$ ?

-

In the first place not the rules of algebra (distributivity, $\ldots$) apply here, but the rules of describing sets. If you are given a nested sum $$\Sigma:=\sum_{j=a}^b \ \sum_{k=c(j)}^{d(j)} z_{j,k}\ ,$$ each individual summand $z_{k,j}$ depends on the outer variable $j$ as well as on the inner variable $k$. Sometimes a factor depending only on the outer variable $j$ can be pulled out, but forget this at the moment.

The essential point is to get a clear picture of the set $$S:=\{(j,k)\ |\ a\leq j\leq b,\ c(j)\leq k\leq d(j)\}$$ of lattice points in the $(j,k)$-plane over which the double sum $\Sigma$ ranges. To this end draw such a plane with a horizontal $j$-axis and a vertical $k$-axis and shade the "region" $S$.

In most cases this region will be convex. This facilitates the rearranging of the double sum $\Sigma$ when we want $k$ to become the outer variable and $j$ the inner variable. There will be a $k_\min:=\min\{k\ |\ \exists j:\ (j,k)\in S\}$ and similarly a $k_\max:=\max\{k\ |\ \exists j:\ (j,k)\in S\}$, and for each integer $k\in[k_\min\ .\, .\ k_\max]$ there are two well defined numbers $a(k)$, $b(k)$, such that $$\{j\in{\mathbb Z}\ |\ (j,k)\in S\}=[a(k)\ .\, .\ b(k)]\ .$$ It follows that $$\Sigma\ =\ \sum_{k=k_\min}^{k_\max}\ \sum_{j=a(k)}^{b_k} z_{j,k}\ .$$ Now let's turn to your example. Here the set $S$ is given by $$S:=\{(t,u)\in {\mathbb Z}^2\ |\ 1\leq t\leq T,\ t\leq u\leq T\}$$ and is a "triangle" with vertices $(1,1)$, $(1,T)$, $(T,T)$. It follows that $u_\min=1$, $\ u_\max=T$, and for each given $u\in[u_\min\ .\,.\ u_\max]$ we have $$\{t\in{\mathbb Z}\ |\ (t,u)\in S\}=[1\ .\,.\ u]\ .$$ Therefore your sum $\Sigma$ under the envisaged rearranging becomes \eqalign{\Sigma&=\sum_{u=1}^T\ \sum_{t=1}^u Z(u)(1+i)^{-u}\cr &=\sum_{u=1}^T\left( Z(u)(1+i)^{-u}\sum_{t=1}^u 1\right)\cr &=\sum_{u=1}^T u Z(u)(1+i)^{-u}\ .\cr} As $z_{t,u}:=Z(u)(1+i)^{-u}$ did not depend on the inner summation variable $t$ we could pull $z_{t,u}$ out of the inner sum which then became $\sum_{t=1}^u 1= u$.

-
Is there a reference to this method you proposed? Thanks! – A friendly helper Jul 5 '13 at 21:40
@A friendly helper: It's all explained in my answer. This sort of computation is done all the time, and is in a way "precalculus stuff". – Christian Blatter Jul 6 '13 at 8:08

If we look at it for $T=1$:

$$\sum_{t=1}^{1}{\sum_{u=t}^{1}(Z(u)\cdot(1+i)^{-u})}=Z(1)\cdot(1+i)^{-1}$$

For $T=2$:

$$\sum_{t=1}^{2}{\sum_{u=t}^{2}{Z(u)\cdot(1+i)^{-u})}}=(Z(1)\cdot(1+i)^{-1}+Z(2)\cdot(1+i)^{-2})+(Z(2)\cdot(1+i)^{-2})\\=Z(1)\cdot(1+i)^{-1}+2(Z(2)\cdot(1+i)^{-2})$$

For $T=3$:

$$\sum_{t=1}^{3}{\sum_{u=t}^{3}{(Z(u)\cdot(1+i)^{-u})}}=(Z(1)\cdot(1+i)^{-1}+Z(2)\cdot(1+i)^{-2}+Z(3)\cdot(1+i)^{-3})+(Z(2)\cdot(1+i)^{-2}+Z(3)\cdot(1+i)^{-3})+(Z(3)\cdot(1+i)^{-3})\\= Z(1)\cdot(1+i)^{-1}+2(Z(2)\cdot(1+i)^{-2})+3(Z(3)+(1+i)^{-3})$$

This suggests a general form:

$$\sum_{t=1}^{T}\sum_{u=t}^{T}(Z(u)\cdot(1+i)^{-u})=Z(1)\cdot(1+i)^{-1}+2(Z(2)\cdot(1+i)^{-2})+\cdots+T(Z(T)\cdot(1+i)^{-T})$$

Or equivalently: $$\sum_{t=1}^{T}\sum_{u=t}^{T}(Z(u)\cdot(1+i)^{-u})=\sum_{n=1}^{T}\frac{nZ(n)}{(1+i)^{n}}$$

We can prove this by induction (we have already proved the basis case for $T=1$), by assuming that the proposition holds for $T=n$ and proving that therefore also must hold for $T=n+1$:

$$\sum_{t=1}^{n+1}\sum_{u=t}^{n+1}(Z(u)\cdot(1+i)^{-u})=\sum_{t=1}^{n}\sum_{u=t}^{n}(Z(u)\cdot(1+i)^{-u})+(n+1)(Z(n+1)\cdot(1+i)^{-(n+1)})\\ =Z(1)\cdot(1+i)^{-1}+2(Z(2)+(1+i)^{-2})+\cdots+n(Z(n)\cdot(1+i)^{-n})+(n+1)(Z(n)\cdot(1+i)^{-(n+1)}$$

Therefore, as $T=n\implies T=n+1$ holds, and the proposition holds for $n=1$, by induction we have shown that the general form holds $\forall T\in\mathbb{N}$.

I don't know if a nice closed form exists for your last sum though.

-

$\sum_{t=1}^T t \cdot Z(t) \cdot (1+i)^{-t}$

is correct for all $T$ and not just $T=3$. There is a pattern that every $Z(t) \cdot (1+i)^{-t}$ is appearing $t$ times.

It depends on the terms in the expression. In

$\sum_{t=1}^{T}\sum_{u=t}^{T} Z(u) \cdot (1+i)^{-u+t}$,

you have both variable $u$ and $t$ in the same term so it breaks that straightforward pattern to wrap it all up in terms of $t$. You still can write it more compactly tough:

$\sum_{u=1}^T Z(u) \cdot (\sum_{t=u}^T (1+i)^{-u+t})$.

Just expand it with terms and see the pattern there is.

-