0
$\begingroup$

Let $z=e^{i\omega }, \omega \in \mathbb{R}$ find a closed form for:

$$ f_N(\omega)=\frac{1}{N} \sum_{\ell=1}^{N} \sum_{k=1}^{N}z^{\ell-k}\min\{\ell,k\}$$

I'm aware there suppose to be a neat closed form using the sine kernel, yet I can't get there.

I exploited symmetry and reached:

$$\frac{2}{N}\Re\left\{ \sum_{\ell=1}^{N}\sum_{k=1}^{\ell}z^{\ell-k}k\right\} - \frac{N+1}{2} $$

I couldn't find a way to express the inner sum but as the derivative of the geometric series multiplied by z, and from there the expression didn't simplify.

$\endgroup$
2
  • 1
    $\begingroup$ I think your second expression counted the $k=\ell$ terms twice: you have $N^2$ terms in the first expression but $N^2+N$ terms in the second. $\endgroup$ Mar 5, 2020 at 22:20
  • $\begingroup$ OK, but I think you have to divide that correction sum by $N$ as well. $\endgroup$ Mar 6, 2020 at 14:11

3 Answers 3

2
$\begingroup$

I don't think the symmetry stuff helped much. I started with $$\begin{align}nx^n&=\frac{(n+1)x^{n+1}-nx^n}{x-1}-\frac x{(x-1)^2}(x^{n+1}-x^n)\\ x^n&=\frac{x^{n+1}-x^n}{x-1}\\ 1&=(n+1)-n\end{align}$$ So now I was ready to sum $$\begin{align}\sum_{k=1}^Nz^{-k}\min(k,\ell)&=\sum_{k=1}^{\ell}kz^{-k}+\sum_{k=\ell+1}^N\ell z^{-k}\\ &=\sum_{k=1}^{\ell}\left[\frac{(k+1)z^{-k-1}-kz^{-k}}{z^{-1}-1}-\frac{z^{-1}}{(z^{-1}-1)^2}\left(z^{-k-1}-z^{-k}\right)\right]\\ &\quad+\ell\sum_{k=\ell+1}^N\frac{z^{-k-1}-z^{-k}}{z^{-1}-1}\\ &=\frac{(\ell+1)z^{-\ell-1}-z^{-1}}{z^{-1}-1}-\frac{z^{-1}}{(z^{-1}-1)^2}\left(z^{-\ell-1}-z^{-1}\right)\\ &\quad+\frac{\ell}{z^{-1}-1}\left(z^{-N-1}-z^{-\ell-1}\right)\\ &=\ell\left(\frac{z^{-N-1}}{z^{-1}-1}\right)+z^{-\ell}\left(\frac{-z^{-1}}{(z^{-1}-1)^2}\right)+\left(\frac{z^{-1}}{(z^{-1}-1)^2}\right)\end{align}$$ Now we can do $$\begin{align}f_N(\omega)&=\frac1N\sum_{\ell=1}^Nz^{\ell}\sum_{k=1}^Nz^{-k}\min(k,\ell)\\ &=\frac1N\left(\frac{z^{-1}}{(z^{-1}-1)^2}\right)\sum_{\ell=1}^N\left\{(z^{-1}-1)z^{-N}\ell z^{\ell}-1+z^{\ell}\right\}\\ &=\frac1N\left(\frac{z}{(z-1)^2}\right)\sum_{\ell=1}^N\left\{-\frac{z-1}zz^{-N}\left[\frac{(\ell+1)z^{\ell+1}-\ell z^{\ell}}{z-1}-\frac z{(z-1)^2}\left(z^{\ell+1}-z^{\ell}\right)\right]\right.\\ &\quad\left.-[(\ell+1)-\ell]+\frac{z^{\ell+1}-z^{\ell}}{z-1}\right\}\\ &=\frac1N\left(\frac{z}{(z-1)^2}\right)\left\{-\frac{z-1}zz^{-N}\left[\frac{(N+1)z^{N+1}-z}{z-1}-\frac z{(z-1)^2}\left(z^{N+1}-z\right)\right]\right.\\ &\quad\left.-[(N+1)-1]+\frac{z^{N+1}-z}{z-1}\right\}\\ &=\frac1N\left(\frac{z}{(z-1)^2}\right)\left\{-2N-1-\frac1{z-1}z^{-N}+\frac z{z-1}z^N\right\}\\ &=\frac1N\left(\frac1{(z^{1/2}-z^{-1/2})^2}\right)\left\{-2\left(N+\frac12\right)+\frac1{z^{1/2}-z^{-1/2}}\left(z^{N+\frac12}-z^{-N-\frac12}\right)\right\}\\ &=\frac1{4N\sin^2\frac{\omega}2}\left\{2\left(N+\frac12\right)-\frac{\sin\left(N+\frac12\right)\omega}{\sin\frac{\omega}2}\right\}\end{align}$$ A nice result! Let's check it. Here's my Matlab program:

% sum2.m

clear all;
close all;
N = 7;
omega_array = linspace(0.1,3.0,100);
y = zeros(size(omega_array));
x = zeros(size(omega_array));
for j = 1:length(omega_array),
    omega = omega_array(j);
    z = exp(i*omega);
    for L = 1:N,
        for k = 1:N,
            y(j) = y(j)+z^(L-k)*min(L,k);
        end
    end
    y(j) = y(j)/N;
    x(j) = 1/(4*N*sin(omega/2)^2)*(2*(N+1/2)-sin((N+1/2)*omega)/sin(omega/2));
end
plot(omega_array,x,'r-',omega_array,real(y),'b--');
title(['Check for Summation Result, N = ' num2str(N)]);
xlabel('\omega');
ylabel('f_N(\omega)');
legend('Formula','Direct Sum');

And its output:
fig. 1
So it looks OK.

$\endgroup$
1
$\begingroup$

$$\frac{2}{N}\Re\left\{ \sum_{\ell=1}^{N}\sum_{k=1}^{\ell}z^{\ell-k}k\right\} $$ =$$\frac{2}{N}\Re\left\{ \sum_{\ell=1}^{N} z^{\ell-1}\sum_{k=1}^{\ell}z^{1-k}k\right\} $$ We have : $$\left\{\sum_{k=1}^{\ell}z^{1-k}k\right\} =-(\frac{1-1/z^l}{1-1/z})'$$

and : $$z^{\ell-1} (\frac{1-1/z^l}{1-1/z})'=(z^{\ell-1}\frac{1-1/z^l}{1-1/z})'-(\frac{1-1/z^l}{1-1/z})(z^{\ell-1})'$$

Therefore : $$\frac{2}{N}\Re\left\{ \sum_{\ell=1}^{N} z^{\ell-1}\sum_{k=1}^{\ell}z^{1-k}k\right\} $$ =$$\frac{2}{N}\Re\left\{ \sum_{\ell=1}^{N}((z^{\ell-1}\frac{1-1/z^l}{1-1/z})'-(\frac{1-1/z^l}{1-1/z})(z^{\ell-1})')\right\} $$ =$$\frac{2}{N}\Re\left\{ \sum_{\ell=1}^{N}((z^{\ell-1}\frac{1-1/z^l}{1-1/z})'-\sum_{\ell=2}^{N}(\frac{1-1/z^l}{1-1/z})(z^{\ell-1})')\right\} $$ =$$\frac{2}{N}\Re\left\{ \sum_{\ell=1}^{N}((z^{\ell-1}\frac{1-1/z^\ell}{1-1/z})'-\sum_{\ell=2}^{N}(\frac{1-1/z^\ell}{1-1/z})(z^{\ell-1})')\right\} $$ =$$\frac{2}{N}\Re\left\{ \sum_{\ell=1}^{N}(\frac{z^{\ell}-1}{z-1})'-\sum_{\ell=2}^{N}\frac{\ell-1}{z}(\frac{z^{\ell}-1}{z-1})\right\} $$

=$$\frac{2}{N}\Re\left\{ (\sum_{\ell=1}^{N}\frac{z^{\ell}-1}{z-1})'-\frac {1}{z(z-1)}\sum_{\ell=2}^{N}(\ell-1)(z^{\ell}-1)\right\} $$ =$$\frac{2}{N}\Re\left\{ (\frac{z^{N+1}-z-N(z-1)}{(z-1)^2})'-\frac {1}{z(z-1)}\sum_{\ell=1}^{N-1}\ell(z^{\ell+1}-1)\right\} $$ =$$\frac{2}{N}\Re\left\{ (\frac{z^{N+1}-z-N(z-1)}{(z-1)^2})'-\frac {1}{z(z-1)}(\sum_{\ell=1}^{N-1}\ell z^{\ell+1}-\sum_{\ell=1}^{N-1}1)\right\} $$ =$$\frac{2}{N}\Re\left\{ (\frac{z^{N+1}-z-N(z-1)}{(z-1)^2})'-\frac {z}{(z-1)}(\sum_{\ell=0}^{N-1}\ell z^{\ell-1})-\frac {1}{z(z-1)}\sum_{\ell=1}^{N-1}1)\right\} $$ =$$\frac{2}{N}\Re\left\{ (\frac{z^{N+1}-z-N(z-1)}{(z-1)^2})'-\frac {z}{(z-1)}(\frac{z^N-1}{z-1})'-\frac {1}{z(z-1)}\sum_{\ell=1}^{N-1}1)\right\} $$ =$$\frac{2}{N}\Re\left\{ (\frac{z^{N+1}-z-N(z-1)}{(z-1)^2})'-\frac {z-1+1}{(z-1)}(\frac{z^N-1}{z-1})'-\frac {1}{z(z-1)}\sum_{\ell=1}^{N-1}1)\right\} $$ =$$\frac{2}{N}\Re\left\{ (\frac{z^{N+1}-z-N(z-1)-(z^N-1)(z-1))}{(z-1)^2})'-\frac {1}{(z-1)}(\frac{z^N-1}{z-1})'-\frac {1}{z(z-1)}\sum_{\ell=1}^{N-1}1)\right\} $$ =$$\frac{2}{N}\Re\left\{ (\frac{z^N-1-N(z-1)}{(z-1)^2})'-\frac {1}{(z-1)}(\frac{z^N-1}{z-1})'-\frac {1}{z(z-1)}\sum_{\ell=1}^{N-1}1)\right\} $$

=$$\frac{2}{N}\Re\left\{ (\frac{z^N-1-N(z-1)}{(z-1)^2})'-(\frac{z^N-1}{(z-1)^2})'+(\frac {1}{(z-1)})'(\frac{z^N-1}{(z-1)})-\frac {1}{z(z-1)}\sum_{\ell=1}^{N-1}1\right\} $$

=$$\frac{2}{N}\Re\left\{ (\frac{-N}{(z-1)})'+(\frac {1}{(z-1)})'(\frac{z^N-1}{(z-1)})-\frac {1}{z(z-1)}\sum_{\ell=1}^{N-1}1\right\} $$ =$$\frac{2}{N}\Re\left\{ (\frac{Nz'}{(z-1)^2})+(\frac {z'}{(z-1)^2})(\frac{z^N-1}{z-1})-\frac {N-1}{z(z-1)}\right\} $$

$$z^N-1= 2 i sin(Nw/2)z^{N/2}$$ and $$z'=iwz$$

=$$\frac{2}{N}\Re\left\{ (\frac{-Niw}{2sin^2(Nw/2)})+(\frac {-iwz}{4sin^2(Nw/2)})(\frac{sin(Nw/2)}{sin(w/2)})e^{(N-1)iw/2}-\frac {N-1}{2 i sin(w/2)e^{3iNw/2}}\right\} $$

Therefore :

$$f_N(w)=\frac{2}{N}\left\{ (\frac {-w}{4sin^2(Nw/2)})(\frac{sin(Nw/2)}{sin(w/2)})cos((N+1)w/2)-\frac {(N-1)sin({3Nw/2})}{2 sin(w/2)}\right\}$$

$\endgroup$
1
  • $\begingroup$ Thank you, sir, for spending your time answering. $\endgroup$
    – Prim3L0v3r
    Mar 5, 2020 at 21:33
0
$\begingroup$

To show another way

$$ \eqalign{ & \sum\limits_{l = 1}^N {\sum\limits_{k = 1}^l {kz^{\,l - k} } } = \sum\limits_{1\, \le \,k\, \le \,l\, \le \,N} {kz^{\,l - k} } = \sum\limits_{1\, \le \,\,l\, \le \,N} {z^{\,l} } \sum\limits_{1\, \le \,k\, \le \,l\,} {kz^{\, - k} } = \cr & = \sum\limits_{1\, \le \,\,l\, \le \,N} {z^{\,l + 1} } \sum\limits_{1\, \le \,k\, \le \,l\,} {kz^{\, - k - 1} } = - \sum\limits_{1\, \le \,\,l\, \le \,N} {z^{\,l + 1} \left( {{d \over {dz}}\sum\limits_{1\, \le \,k\, \le \,l\,} {z^{\, - k} } } \right)} = \cr & = - \sum\limits_{1\, \le \,\,l\, \le \,N} {z^{\,l + 1} \left( {{d \over {dz}}\left( {{1 \over z}{{1 - \left( {1/z} \right)^{\,l} } \over {1 - \left( {1/z} \right)}}} \right)} \right)} = \cr & = - \sum\limits_{1\, \le \,\,l\, \le \,N} {z^{\,l + 1} } \left( {{d \over {dz}}\left( {{{z^{\,l} - 1} \over {z^{\,l} \left( {z - 1} \right)}}} \right)} \right) = \cr & = {1 \over {\left( {z - 1} \right)^{\,2} }}\sum\limits_{1\, \le \,\,l\, \le \,N} {l\left( {1 - z} \right) - z + z^{\,l + 1} } = \cr & = {{{{N\left( {N + 1} \right)} \over 2}\left( {1 - z} \right) - Nz + z^{\,2} {{\left( {z^{\,N} - 1} \right)} \over {\left( {z - 1} \right)}}} \over {\left( {z - 1} \right)^{\,2} }} = \cr & = {{ - N\left( {N + 1} \right)\left( {1 - z} \right)^{\,2} - 2Nz\left( {z - 1} \right) + 2z^{\,2} \left( {z^{\,N} - 1} \right)} \over {2\left( {z - 1} \right)^{\,3} }} = \cr & = {{\left( {2z^{\,N} - \left( {N + 1} \right)\left( {N + 2} \right)} \right)z^{\,2} + 2N\left( {N + 2} \right)z - N\left( {N + 1} \right)} \over {2\left( {z - 1} \right)^{\,3} }} \cr} $$

But take care that passing from the first expression to the second, you overcounted the case when $l=k$, which shall not be doubled.
So from the above you have to deduct $$ \sum\limits_{l = 1}^N l $$ to get the first expression

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.