The question I need help with is:

Prove that $$\sum_{k=0}^{6}\frac{1-z^{2}}{1-2z\cos\left(\frac{2k\pi}{7}\right)+z^{2}}=\frac{7(z^{7}+1)}{1-z^{7}}$$

I have already tried brute forcing this by combining the LHS into a single fraction. While this worked, it is an extremely long proof.

I was wondering if there is a more elegant approach that uses partial fractions. I tried decomposing each term in the sum of the LHS into $$-1+\frac{B}{z-\omega^{k}}+\frac{C}{z-\omega^{-k}}$$but this gave me very complicated expressions for constants B and C so I gave up.

  • 1
    $\begingroup$ The claim, as you've stated it here, is incorrect. This can be seen easily by setting $z = 0$. Then the two sides of the equation each give a result of $7$, but the supposed decomposition of the LHS gives a result of $0$. $\endgroup$ – Paul Sinclair Jul 10 '18 at 23:28

We will reduce the following sum (note the value $n$ instead of $7$ cfr. OP):

$$\mathcal{S}=\sum_{k=0}^{n-1}\frac{1-z^2}{1-2z\cos\left(\frac{2\pi i k}{n}\right)+z^2}$$

In this answer, we will make use of the following:

  1. The roots of the polynomial $z^n-1$ are $\left\{\omega^k:k=0,\cdots,n-1\right\}$ with: $$\omega=\exp\left(\frac{2\pi i}{n}\right)$$ and $\omega^{-k}=\omega^{n-k}$.

  2. The fundamental theorem of algebra: $$ z^n-1 = \prod_{k=0}^{n-1}(z-\omega^k)$$

  3. The geometric series: $$g(z)=1+z+z^2+\cdots+z^{n-1}=\frac{z^n-1}{z-1}$$

  4. Using (3), you find that \begin{align} g(\omega^k)=n&,\quad\textrm{if }k\textrm{ is a multiple of }n\\ g(\omega^k)=0&,\quad\textrm{if }k\textrm{ is not a multiple of }n \end{align}

Step 1: Rewrite the denominator as: $(z-\omega^k)(z-\omega^{-k})$ :


Step 2: Split the fraction into two parts making use of

$$\frac{z^2-1}{z-\omega^k}=z + \frac{\omega^k(z-\omega^{-k})}{z-\omega^k},$$

which is obtained by long-division and leads to

$$ \mathcal{S}=-\sum_{k=0}^{n-1}\frac{z}{z-\omega^{-k}} - \sum_{k=0}^{n-1}\frac{\omega^k}{z-\omega^k}.$$

Step 3: Using (1), redfine the indices of the first sum ($n-k=k'$) and merge it with the second to reduce $\mathcal{S}$ into:

$$ \mathcal{S}=-\sum_{k=0}^{n-1}\frac{z+\omega^k}{z-\omega^k}.$$

Step 4: It is clear that this sum $\mathcal{S}$ is a rational function of two polynomials $p(z)$ and $q(z)$. The denominator $q(z)$ is quickly obtained from the fundamental theorem of algebra (2) when merging all fractions in $\mathcal{S}$. This gives

$$\mathcal S=-\frac{p(z)}{q(z)},\qquad\textrm{with}\qquad q(z)=z^n-1=\prod_{k=0}^{n-1}(z-\omega^k)$$

The polynomial $p(z)$ is then given by :

$$ p(z)=\sum_{k=0}^{n-1} (z+\omega^k) r_k(z), \qquad\textrm{with}\qquad r_k(z)=\frac{q(z)}{z-\omega^k}=\frac{z^n-1}{z-\omega^k}. $$

Step 5: Using the geometric Series $g(z)$ cfr.(3), we can write:


and thus

$$ r_k(z)=\omega^{-k}\left(1+\frac{z}{\omega^k}+\cdots+\frac{z^{n-1}}{\omega^{k(n-1)}}\right)=\omega^{-k}\sum_{m=0}^{n-1}\left(\frac{z}{\omega^k}\right)^m,$$

Step 6: Finaly we can determine $p(z)$ by looking at the powers of $z$. Plugging the values of $r_k(z)$ into the equation for $p(z)$ gives us:

$$p(z) = \sum_{k=0}^{n-1}\sum_{m=0}^{n-1}\left(\left(\frac{z}{\omega^k}\right)^{m+1} + \left(\frac{z}{\omega^k}\right)^{m}\right).$$

and making use of (4) we finally obtain

$$p(z) = n(z^n+1)$$

Which demonstrates that:

$$\bbox[5px,border:2px solid #00A000]{ \mathcal{S}=\sum_{k=0}^{n-1}\frac{1-z^2}{1-2z\cos\left(\frac{2\pi i k}{n}\right)+z^2} = -\frac{p(z)}{q(z)} = \frac{n(z^n+1)}{1-z^n}}$$


Following the posts that were first to appear we introduce $\zeta=\exp(2\pi i/n)$ and seek to evaluate

$$S = \sum_{k=0}^{n-1} \frac{1-z^2}{(z-\zeta^k)(z-1/\zeta^k)}.$$

where presumably $z$ is not a power of $\zeta$ and no singularity appears. Introducing

$$f(v) = \frac{1-z^2}{(z-v)(z-1/v)} \frac{n/v}{v^n-1} = \frac{1-z^2}{(z-v)(vz-1)} \frac{n}{v^n-1} \\ = -\frac{1}{z} \frac{1-z^2}{(v-z)(v-1/z)} \frac{n}{v^n-1}$$

we have

$$S = \sum_{k=0}^{n-1} \mathrm{Res}_{v=\zeta^k} f(v).$$

The residue at infinity is zero by inspection and since residues sum to zero we get

$$S = - \mathrm{Res}_{v=z} f(v) - \mathrm{Res}_{v=1/z} f(v).$$

This yields

$$\frac{1}{z} \frac{1-z^2}{z-1/z} \frac{n}{z^n-1} + \frac{1}{z} \frac{1-z^2}{1/z-z} \frac{n}{1/z^n-1} \\ = \frac{1-z^2}{z^2-1} \frac{n}{z^n-1} + \frac{1-z^2}{1-z^2} \frac{z^n n}{1-z^n} = \frac{n}{1-z^n} + \frac{z^n n}{1-z^n}.$$

We obtain

$$\bbox[5px,border:2px solid #00A000]{ S=n\frac{1+z^n}{1-z^n}.}$$

  • $\begingroup$ Very nice solution by using Residues. $\endgroup$ – kvantour Jul 11 '18 at 16:11

A proof can be constructed with the generating function for the Chebyshev polynomials of the first kind. The nice thing is that it suggests another closed-form sum which will be presented at the conclusion.

$$S_n(\color{red}{2})=\sum_{k=0}^{n-1} \frac{1-z^2}{1-2z\cos{(\color{red}{2}\pi k/n)}+z^2} = \sum_{k=0}^{n-1} \Big( 1+2\sum_{m=1}^\infty z^m\,T_m(\cos{(2\pi k/n))} \Big)= $$ $$=n+2 \sum_{m=1}^\infty z^m \sum_{k=0}^{n-1}\cos{k\,x_{m,n}}= n+\sum_{m=1}^\infty z^m\Big(1-\cos{n \,x_{m,n}} + \cot{\frac{x_{m,n}}{2}}\, \sin{n\,x_{m,n}}\Big) $$ where for this problem, $x_{m,n}=2\pi\,m/n.$ From the 2nd to 3rd equality an explicit sum has been performed, a property of the Chebyshev polys with cosine arguments has been used, and an interchange of summations has been performed. The closed-form for the cosine sum can be considered a consequence of the geometric series. Now $\cos{n \,x_{m,n}} = \cos{2\pi m} =1$ so the first two terms within the parentheses cancel. With trig ID's it can be seen that the last term is 0 unless m is a multiple of n. (Note: assume m non-integer and take the limit.) When m is a multiple of n, the term has a value of 2n. Thus $$\sum_{k=0}^{n-1} \frac{1-z^2}{1-2z\cos{(2\pi k/n)}+z^2} = n+2n\sum_{m=1}^\infty z^{n\,m} =n\big(1+\frac{2z^n}{1-z^n}\big)=n\frac{1+z^n}{1-z^n}.$$ Analagous steps for $x_{m,n}=\pi\,m/n.$ lead to $$S_n(\color{red}{1})=\sum_{k=0}^{n-1} \frac{1-z^2}{1-2z\cos{(\color{red}{1}\pi k/n)}+z^2} =n\,\frac{1+z^{2n}}{1-z^{2n}}+\frac{2z}{1-z^2} $$


(Edit: the following was posted before the OP added "I have already tried brute forcing this ...".)

I don't see the elegant solution offhand, but the problem can certainly be brute-forced as sketched below. Note that the first term of the sum (excluding the $\,\,1-z^2$ factor ) is $\,\dfrac{1}{(z-1)^2}\,$ then the rest of terms are pairwise equal since $\,\cos \left(2k\pi/7\right) = \cos\left(2(7-k)\pi/7)\right)\,$. Therefore the sum of those remaining $\,6\,$ terms is twice the sum of the first $\,3\,$, which works out to:

$$ \begin{align} & \frac{1}{z^2-(\omega+\omega^6)z+1}+\frac{1}{z^2-(\omega^2+\omega^5)z+1}+\frac{1}{z^2-(\omega^3+\omega^4)z+1} \\[15px] =\;\; &{\frac{(z^2-(\omega^2+\omega^5)z+1)(z^2-(\omega^3+\omega^4)z+1)\\+(z^2-(\omega+\omega^6)z+1)(z^2-(\omega^3+\omega^4)z+1)\\+(z^2-(\omega+\omega^6)z+1)(z^2-(\omega^2+\omega^5)z+1)}{(z-\omega)(z-\omega^6)\cdot(z-\omega^2)(z-\omega^5) \cdot (z-\omega^3)(z-\omega^4)}} \end{align} $$

The denominator of the latter fraction is $\,\dfrac{z^7-1}{z-1}\,$, and the numerator eventually evaluates to:

$$ 3z^4 -2(\omega^6+\omega^5+\omega^4+\omega^3+\omega^2+\omega)z^3 \\+(\omega^{11}+\omega^{10}+2\omega^9+2\omega^8+2\omega^6+2\omega^5+\omega^4+\omega^3+6)z^2 \\-2(\omega^6+\omega^5+\omega^4+\omega^3+\omega^2+\omega)z +3 $$

Using that $\,\omega^7=1\,$ and $\,1+\omega+\omega^2+\omega^3+\omega^4+\omega^5+\omega^6=0\,$ the above simplifies to:

$$ 3z^4 +2z^3 +4z^2 +2z +3 $$

Then the problem reduces to verifying the algebraic identity:

$$ (1-z^2)\left(\frac{1}{(z-1)^2} + 2\cdot\frac{3z^4+2z^3+4z^2+2z+3}{\dfrac{z^7-1}{z-1}}\right) = \dfrac{7(z^7+1)}{1-z^7} $$


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.