bound for double sum

Question

How to show that for any constant $\mu \in (0,1)$ the following inequality holds \begin{equation} \sum_{t=M}^N \sum_{s=M}^N \mu^{|t-s|} \leq C (N-M) \end{equation} in which $C$ is a constant that might depend on $\mu$.

I started as follows: write \begin{align} \sum_{t=M}^N \sum_{s=M}^N \mu^{|t-s|} &= \sum_{t=M}^N \left( \sum_{s=M}^{t-1} \mu^{|t-s|} + \sum_{s=t}^t \mu^{|t-s|} + \sum_{s=t+1}^N \mu^{|t-s|} \right)\\ &= \sum_{t=M}^N \sum_{s=t}^{t} \mu^{|t-s|} +\sum_{t=M}^N \left( \sum_{s=M}^{t-1} \mu^{|t-s|}+ \sum_{s=t+1}^N \mu^{|t-s|} \right)\\ & = (M-N) + \sum_{t=M}^N \left( \sum_{s=M}^{t-1} \mu^{|t-s|} + \sum_{s=t+1}^N \mu^{|t-s|} \right) \end{align} Not sure how to get a multiplicative constant $C$ (independent of $N$ and $M$) to establish the inequality.

EDIT: few more steps. From above we see that

\begin{align} \sum_{t=M}^N \sum_{s=M}^N \mu^{|t-s|} &= (M-N) + \sum_{t=M}^N \left( \sum_{s=M}^{t-1} \mu^{|t-s|} + \sum_{s=t+1}^N \mu^{|t-s|} \right) \end{align} Now consider \begin{equation} \left( \sum_{s=M}^{t-1} \mu^{|t-s|} + \sum_{s=t+1}^N \mu^{|t-s|} \right) \end{equation} Because $\mu\in(0,1)$, the maximum term in each of these two sums are $\mu^{|t-(t-1)|} = \mu$ and $\mu^{|t-(t+1)|} = \mu$ respectively. Therefore we can have the following bound \begin{equation} \left( \sum_{s=M}^{t-1} \mu^{|t-s|} + \sum_{s=t+1}^N \mu^{|t-s|} \right) \leq \left( \mu \sum_{s=M}^{t-1} 1 + \mu \sum_{s=t+1}^N 1 \right) = \mu ( |t-1 -M| + |N - t-1|) \end{equation}

now applying the second sum it seems that I get \begin{equation} \mu \sum_{t=M}^N \left(\sum_{s=M}^{t-1} 1 + \sum_{s=t+1}^N 1 \right)\stackrel{?}{\leq} 2\mu (N-M-1) \end{equation}

Answer 1

You're almost there. In the expression \begin{equation} \sum_{s=M}^{t-1} \mu^{|t-s|} + \sum_{s=t+1}^N \mu^{|t-s|} \end{equation} both sums are geometric sums with common ratio $\mu$ and largest term $\mu$. Go nuts and upper bound each sum by the infinite sum $$ \mu+\mu^2+\mu^3+\cdots =\frac\mu{1-\mu}, $$ which is a constant depending on $\mu$ but not on $M$ and $N$.

I suspect the RHS of the putative inequality should be $C(N-M+1)$. (Look at the case $M=N$.) The above argument gives $$C=1+\frac{2\mu}{1-\mu}=\frac{1+\mu}{1-\mu}.$$

Answer 2

Write the sum as

$$(N-M+1)\cdot\mu^0+2\cdot(N-M)\cdot\mu^1+2\cdot(N-M-1)\cdot\mu^2+\dots+2\cdot1\cdot\mu^{N-M}\\ =(N-M+1)+2\,\sum_{k=1}^{N-M}\,(N-M+1-k)\cdot\mu^k$$

With $N-M=t$, we would like to find an upper bound for

$$f(t)=\frac{t+1}t+2\,\sum_{k=1}^{t}\,\frac{t+1-k}{t}\cdot\mu^k$$

where $t\in \mathbb{N}^*$ Now, observe that

\begin{align} f(t)&\leq \frac{t+1}t+2\,\sum_{k=1}^{t}\,\frac{t+1}{t}\cdot\mu^k\\ &=\frac{t+1}t\left(1+2\,\sum_{k=1}^t\mu^k\right), \end{align}

which implies that

\begin{align} \limsup_{t\to\infty}f(t) &\leq \limsup_{t\to\infty}\frac{t+1}t\left(1+2\,\sum_{k=1}^t\mu^k\right)\\ &=\lim_{t\to\infty}\frac{t+1}t\left(1+2\,\sum_{k=1}^t\mu^k\right)\\ &=1+\frac{2\mu}{1-\mu}=\frac{1+\mu}{1-\mu} \end{align}

In particular, $\{f(t)\}_{t\in\mathbb{N}^*}$ is bounded, so we may take $C=\max\{f(t)\}_{t\in\mathbb{N}^*}$.

Answer 3

$$\newcommand{\s}[1]{\sum_{s=M}^{#1}}$$

We can use the formula $$$$If $p_{k,l}=p_{l,k}$ $$$$$$\sum_{k=a}^{b}\sum_{l=a}^{b} p_{k,l}=\sum_{k=l=a}^{b} p_{k,l}+2\sum_{a\le k\lt l\lt b}^{} p_{k,l}$$

Let, $$\mu=e$$ Where $e$ is a variable, As,$$e^{|t-s|}=e^{|s-t|}$$we can write, $$\sum_{t=M}^N \sum_{s=M}^N \mu^{|t-s|} $$ $$=\sum_{t=s=M}^N e^0+2\sum_{N\ge t\gt s\ge M}^{N} e^{t-s}$$ $$=N-M+1+2\sum_{N\ge t\gt s\ge M}^{N} e^{t-s}$$ $$=N-M+1+2\sum_{k=M}^{N}(\s{k} e^{k-s})$$ $$=N-M+1+2\sum_{k=M}^{N}(e^k\s{k}e^{-s})$$

$$=N-M+1+2\sum_{k=M}^{N}(e^k e^{M}\frac{(e^{-1})^{k-M+1}-1}{e^{-1}-1})$$ $$=N-M+1+2\frac{e^M}{e^{-1}-1}\sum_{k=M}^{N}(e^k ((e^{-1})^{k-M+1}-1))$$ $$=N-M+1+2\frac{e^M}{e^{-1}-1}\sum_{k=M}^{N}(e^k ((e^{-1})^{k-M+1}-e^{k})$$ $$=N-M+1+2\frac{e^M}{e^{-1}-1}\sum_{k=M}^{N}(e^k ((e^{-1})^{k-M+1}))-2\sum_{k=M}^{N}e^k$$ $$=N-M+1+2\frac{e^M}{e^{-1}-1}\sum_{k=M}^{N}(e^k (e^{-k+M-1})-2\sum_{k=M}^{N}e^k$$ $$=N-M+1+2\frac{e^M}{e^{-1}-1}\sum_{k=M}^{N}(e^{M-1})-2\sum_{k=M}^{N}e^k$$ $$=N-M+1+2\frac{e^M}{e^{-1}-1}\sum_{k=M}^{N}(e^{M-1})-2e^M\frac{e^{N-M+1}-1}{e-1}$$ $$=N-M+1+2\frac{e^M}{e^{-1}-1}(N-M+1)(e^{M-1})-2e^M\frac{e^{N-M+1}-1}{e-1}$$ $$=N-M+1-2\frac{e^{M+1}}{e-1}(N-M+1)(e^{M-1})-2e^M\frac{e^{N-M+1}-1}{e-1}$$ $$=N-M+1-2\frac{e^{2M}}{e-1}(N-M+1)-2\frac{e^{N+1}-e^M}{e-1}$$

$$=(N-M+1)(1-2\frac{e^{2M}}{e-1})-2\frac{e^{N+1}-e^M}{e-1}$$

$$=(N-M+1)(\frac{e-1-2e^{2M}}{e-1})-2\frac{e^{N+1}-e^M}{e-1}$$ $$=\frac{(N-M)(e-1-2e^{2M})-2e^{N+1}+2e^M}{e-1}+\frac{e-1-2e^{2M}-2e^{N+1}+2e^M}{e-1}$$ $$\le \frac{(N-M)(e-1-2e^{2M})-2e^{N+1}}{e-1}$$