Complex Partial Fraction Decomposition

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.

• 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$. 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})$ :

$$\mathcal{S}=\sum_{k=0}^{n-1}\frac{1-z^2}{(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:

$$g\left(\frac{z}{\omega^{k}}\right)=\frac{z^n\omega^{-kn}-1}{z\omega^{-k}-1}={\omega^{k}}\cdot\frac{z^n-1}{z-\omega^k}$$

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

• Very nice solution by using Residues. 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}$$