Closed form for a complex sum

Question

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.

Answer 1

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:

So it looks OK.

Answer 2

$$\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\}$$

Answer 3

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