The sum of triangular functions

Question

I have a sum of $N-1$ triangular functions to calculate and it is $$s = \sum_{q=0}^{N-1} \frac{W_q \left(\cos\left(\dfrac{n\pi q}{N}\right) + \cos\left(\dfrac{(n-1)\pi q}{N}\right)\right) }{ 1 + \cos\left(\dfrac{\pi q}{N}\right)},$$ where $W_q = 1$ except $W_0 = \dfrac12$. It indeed has analytical result $N-n+\dfrac12$ and I can't get it.

Answer 1

I'm going to assume (which seems to be implicit in the question) that $0 < n \le N$. I'm also going to parameterise $s$ for clarity.

Then your expression simplifies to

$$s_{N,n} = \frac12 + \sum_{q=1}^{N-1} \frac{\cos\left(\frac{n\pi q}{N}\right) + \cos\left(\frac{(n-1)\pi q}{N}\right)}{1 + \cos\left(\frac{\pi q}{N}\right)} = \frac12 + \sum_{q=1}^{N-1} \frac{T_n(\cos q\theta_N) + T_{n-1}(\cos q\theta_N)}{1 + \cos q\theta_N}$$ where $\theta_N = \frac{\pi}{N}$ and $T_n$ is the $n$th Chebyshev polynomial (of the first kind).

There's a less well known family of polynomials called the Chebyshev polynomials of the third kind, defined by $$V_0(x) = 1; \qquad V_1(x) = 2x - 1; \qquad V_n(x) = 2xV_{n-1}(x) - V_{n-2}(x)$$

Theorem: for $n > 0$ we have $T_n(x) + T_{n-1}(x) = (1+x)V_{n-1}(x)$. Proof is by induction, using the identity $V_n(x) + V_{n-1}(x) = 2T_n(x)$ from the OEIS link. Then $$s_{N,n} = \frac12 + \sum_{q=1}^{N-1} V_{n-1}(\cos q\theta_N)$$

Note that we only care about the even exponents of $V_n$, because $\sum_{q=1}^{N-1} \cos^{2k+1} q\theta_N = 0$ for integer $k \neq 0$, by matching pairs of $q$ which sum to $N$ and using $\cos q\theta_N = -\cos (N-q)\theta_N$.

From Barry's On the Group of Almost-Riordan Arrays (linked in the OEIS page above) we have $$V_n(x) = \sum_{j=0}^{n/2} (-1)^j B^2_{n-j,j} x^{n-2j} - \sum_{j=0}^{(n-1)/2} (-1)^j B^2_{n-j-1,j} x^{n-2j-1}$$ where $B^2_{n,j} = \sum_i \binom ni \binom ij$. Then filtering to even exponents,

$$\begin{eqnarray*} \sum_{q=1}^{N-1} V_{2k}(\cos q\theta_N) &= & \sum_{j=0}^k (-1)^j B^2_{2k-j,j} \sum_{q=1}^{N-1} \cos^{2(k-j)} q\theta_N \\ \sum_{q=1}^{N-1} V_{2k+1}(\cos q\theta_N) &= -& \sum_{j=0}^k (-1)^j B^2_{2k-j,j} \sum_{q=1}^{N-1} \cos^{2(k-j)} q\theta_N \end{eqnarray*}$$

It's probably simpler to reindex $j$: $$\sum_{q=1}^{N-1} V_{2k}(\cos q\theta_N) = -\sum_{q=1}^{N-1} V_{2k+1}(\cos q\theta_N) = \sum_{j=0}^k (-1)^{k-j} B^2_{k+j,k-j} \sum_{q=1}^{N-1} \cos^{2j} q\theta_N$$

Then

$$s_{N,2k+1} = \frac12 + \sum_{q=1}^{N-1} V_{2k}(\cos q\theta_N) = \frac12 + \sum_{j=0}^k (-1)^{k-j} B^2_{k+j,k-j} \sum_{q=1}^{N-1} \cos^{2j} q\theta_N \\ s_{N,2k+2} = \frac12 + \sum_{q=1}^{N-1} V_{2k+1}(\cos q\theta_N) = \frac12 - \sum_{j=0}^k (-1)^{k-j} B^2_{k+j,k-j} \sum_{q=1}^{N-1} \cos^{2j} q\theta_N$$

Note that since $0 < n \le N$, we certainly have $j \le k = \lfloor \tfrac{n-1}2 \rfloor < N$.

---

Greening showed in A trigonometric summation, Amer. Math. Monthly, 75 (1968), 405-406 that

$$\sum_{k=1}^{\lfloor n/2 \rfloor} 4^\mu \cos^{2\mu} \tfrac{k \pi}{n+1} = (n+1) \binom{2\mu - 1}{\mu - 1} - 2^{2\mu - 1}$$ when $0 < \mu < n+1$.

With suitable substitutions (including $\binom{2j-1}{j-1} = \frac12 \binom{2j}{j}$) we get

$$\sum_{q=1}^{\lfloor (N-1)/2 \rfloor} \cos^{2j} q \theta_N = \frac{1}{2^{2j+1}} \binom{2j}{j} N - \frac12$$ when $0 < j < N$.

By symmetry we fill in the other half; when there's a term for $1 \le q < N$ which isn't accounted for in either then it's $\cos^{2j} \tfrac\pi 2 = 0$. The case $j=0$ is trivial; and we get

$$\sum_{q=1}^{N-1} \cos^{2j} q\theta_N = \frac{1}{2^{2j}} \binom{2j}{j} N - 1$$ when $0 \le j < N$.

---

So under the constraints described,

$$\sum_{j=0}^k (-1)^{k-j} B^2_{k+j,k-j} \sum_{q=1}^{N-1} \cos^{2j} q\theta_N = \sum_{j=0}^k (-1)^{k-j} B^2_{k+j,k-j} \left( \frac{1}{2^{2j}} \binom{2j}{j} N - 1 \right) \\ = \sum_{j=0}^k (-1)^{k-j} \left( \frac{1}{4^j} \binom{2j}{j} N - 1 \right) \sum_i \binom{k+j}{i} \binom{i}{k-j} \\ = \left( \sum_{j=0}^k (-1)^{k-j} \frac{1}{4^j} \binom{2j}{j} \sum_i \binom{k+j}{i} \binom{i}{k-j} \right) N - \sum_{j=0}^k (-1)^{k-j} \sum_i \binom{k+j}{i} \binom{i}{k-j} \\ = N - (2k + 1)$$ where the final binomial sum reduction is handled by a CAS.

So

$$s_{N,2k+1} = \tfrac12 + N - 2k - 1 = N - (2k+1) + \tfrac12 \\ s_{N,2k+2} = \tfrac12 - N + 2k + 1 = -(N - (2k+2) + \tfrac12)$$

or, combining the cases, $$s_{N,n} = (-1)^{n+1} (N - n + \tfrac12)$$ subject to $0 < n \le N$.

Answer 2

Solving for definite $n\in\mathbb{Z}$ I find something a bit more complicated than what is written in the OP:

$$\frac{1}{2}+\sum _{q=1}^{N-1} \frac{\cos (\pi (n-1) q/N)+\cos (\pi n q/N)}{\cos (\pi q/N)+1}=\begin{cases}(-1)^{n}\left(N+n-\frac{1}{2}\right) &\text{if}\;\;n\leq 0,\\ (-1)^{n+1}\left(N-n+\frac{1}{2}\right) &\text{if}\;\;n>0. \end{cases}$$