A congruence involving Chebyshev polynomials

Solution 1:

This is a partial answer.

This answer proves that if $n$ is prime, then $$\sum_{k=0}^{n-1}2T_{n-1}\left(\frac{k}{2}\right) \equiv -1 \pmod n\tag1$$

For $n=2$, $(1)$ holds since $$\sum_{k=0}^{1}2T_{1}\left(\frac{k}{2}\right)=2T_1(0)+2T_1\left(\frac 12\right)=2\cdot 0+2\cdot\frac 12\equiv -1\pmod 2$$

For $n=3$, $(1)$ holds since $$\small\sum_{k=0}^{2}2T_{2}\left(\frac{k}{2}\right)=2T_2(0)+2T_2\left(\frac 12\right)+2T_2(1)=2\cdot (-1)+2\cdot\left(-\frac 12\right)+2\cdot 1\equiv -1\pmod 3$$

In the following, $n$ is prime greater than three.

For $2\le k\le n-1$, using that $\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)=1$, we have $$\small\begin{align}&T_{n-1}\left(\frac{k}{2}\right)\\\\&=\frac 12\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n-1}+\frac 12\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n-1}\\\\&=\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)\left(\frac 12\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n-1}+\frac 12\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n-1}\right)\\\\&=\frac 12\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^n+\frac 12\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^n\\\\&=\frac k4\left(\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n}+\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n}\right)\\\\&\qquad\quad +\frac 12\sqrt{\left(\frac{k}{2}\right)^2-1}\ \left(\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n}-\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n}\right)\end{align}$$

By the binomial theorem, $$\small\begin{align}T_{n-1}\left(\frac{k}{2}\right)&=\frac 12\cdot \frac k2\sum_{i=0}^{n}\binom ni\cdot \left(\frac k2\right)^{n-i}\left(\left(-\sqrt{\left(\frac k2\right)^2-1}\right)^i+\left(\sqrt{\left(\frac k2\right)^2-1}\right)^i\right)\\\\&\qquad\quad +\frac 12\sqrt{\left(\frac k2\right)^2-1}\ \sum_{i=0}^{n}\binom ni\cdot \left(\frac k2\right)^{n-i}\left(\left(-\sqrt{\left(\frac k2\right)^2-1}\right)^i-\left(\sqrt{\left(\frac k2\right)k^2-1}\right)^i\right)\\\\&=\frac 12\cdot \frac k2\sum_{j=0}^{(n-1)/2}\binom{n}{2j}\cdot \left(\frac k2\right)^{n-2j}\cdot 2\left(\sqrt{\left(\frac k2\right)^2-1}\right)^{2j}\\\\&\qquad\quad +\frac 12\sqrt{\left(\frac k2\right)^2-1}\ \sum_{j=1}^{(n+1)/2}\binom{n}{2j-1}\cdot \left(\frac k2\right)^{n-(2j-1)}\cdot (-2)\left(\sqrt{\left(\frac k2\right)^2-1}\right)^{2j-1}\\\\&=\sum_{j=0}^{(n-1)/2}\binom{n}{2j}\cdot \left(\frac k2\right)^{n-2j+1}\left(\left(\frac k2\right)^2-1\right)^{j}-\sum_{j=1}^{(n+1)/2}\binom{n}{2j-1}\cdot \left(\frac k2\right)^{n-(2j-1)}\left(\left(\frac k2\right)^2-1\right)^{j}\end{align}$$

Multiplying the both sides by $2^{n+1}$, we get $$2^{n+1}T_{n-1}\left(\frac{k}{2}\right)=\sum_{j=0}^{(n-1)/2}\binom{n}{2j}\cdot k^{n-2j+1}\left(k^2-4\right)^{j}-\sum_{j=1}^{(n+1)/2}\binom{n}{2j-1}\cdot k^{n-(2j-1)}\left(k^2-4\right)^{j}$$ Since $k^{n+1}=k^2\cdot k^{n-1}\equiv k^2\cdot 1\equiv k^2\pmod n$ for $2\le k\le n-1$ by Fermat's little theorem, and $\binom nj\equiv 0\pmod n$ for $1\le j\le n-1$, we have, for $2\le k\le n-1$, $$4T_{n-1}\left(\frac{k}{2}\right)\equiv k^{n+1}-(k^2-4)^{(n+1)/2}\equiv k^2-(k^2-4)^{(n+1)/2}\pmod n$$

Since this holds for $k=0,1$ as well, we have, letting $N:=\frac{n+1}{2}$, $$\begin{align}\sum_{k=0}^{n-1}4T_{n-1}\left(\frac k2\right)&\equiv \sum_{k=0}^{n-1}\left(k^2-(k^2-4)^{N}\right)\equiv \frac{(n-1)n(2n-1)}{6}-\sum_{k=0}^{n-1}(k^2-4)^{N}\pmod n\\\\&\stackrel{*}\equiv -\sum_{k=0}^{n-1}(k^2-4)^{N}\equiv -(-4)^N-\sum_{k=1}^{n-1}(k^2-4)^{N}\pmod n\\\\&\equiv (-1)^{N+1}\cdot 2^{n+1}-\sum_{k=1}^{n-1}\sum_{j=0}^{N}\binom Nj(k^2)^{j}\cdot (-4)^{N-j}\pmod n\\\\&\equiv (-1)^{N+1}\cdot 4-\sum_{j=0}^{N}\binom Nj(-4)^{N-j}S_{2j}\pmod n\tag2\end{align}$$ where $\stackrel{*}\equiv $ comes from that $(n-1)(2n-1)\equiv 0\pmod 6$, and we defined $S_i$ as $\displaystyle\sum_{k=1}^{n-1}k^i$.

Now, we use the following lemma :

Lemma : $S_0\equiv S_{n-1}\equiv -1\pmod n, S_{n+1}\equiv 0\pmod n$ and $S_i\equiv 0\pmod n$ for $1\le i\le n-2$.

Proof for the lemma :

We have $S_0\equiv \displaystyle\sum_{k=1}^{n-1}1\equiv -1\pmod n$. By Fermat's little theorem, $S_{n-1}\equiv S_0\equiv -1\pmod n$.

Next, let us prove $S_i\equiv 0\pmod n$ for $1\le i\le n-2$ by induction.

The base case : $S_1\equiv \displaystyle\sum_{k=1}^{n-1}k^1\equiv \frac{(n-1)n}{2}\equiv 0\pmod n$.

Suppose that $S_i\equiv 0\pmod n$ for $1\le i\le j$. Since we have $$2^{j+2}-1^{j+2}=\sum_{i=0}^{j+1}\binom{j+2}{i}1^i$$ $$3^{j+2}-2^{j+2}=\sum_{i=0}^{j+1}\binom{j+2}{i}2^i$$ $$\vdots$$ $$n^{j+2}-(n-1)^{j+2}=\sum_{i=0}^{j+1}\binom{j+2}{i}(n-1)^i$$ adding these, we get $$n^{j+2}-1=\sum_{k=1}^{n-1}\sum_{i=0}^{j+1}\binom{j+2}{i}k^i=\sum_{i=0}^{j+1}\binom{j+2}{i}S_i=n-1+(j+2)S_{j+1}+\sum_{i=1}^{j}\binom{j+2}{i}S_i$$ from which we have $$S_{j+1}=\frac{1}{j+2}\left(n^{j+2}-n-\sum_{i=1}^{j}\binom{j+2}{i}S_i\right)$$ By the inductive hypothesis, we see that $S_{j+1}\equiv 0\pmod n$ if $j\le n-3$.

Finally, by Fermat's little theorem, $S_{n+1}\equiv \displaystyle\sum_{k=1}^{n-1}k^{n+1}\equiv \displaystyle\sum_{k=1}^{n-1}k^{2}\equiv S_2\equiv 0\pmod n.\qquad\blacksquare$

Using the lemma, we have, from $(2)$,

$$\begin{align}\sum_{k=0}^{n-1}4T_{n-1}&\equiv (-1)^{N+1}\cdot 4-\sum_{j=0}^{N}\binom Nj(-4)^{N-j}S_{2j}\pmod n\\\\&\equiv (-1)^{N+1}\cdot 4-(-4)^{N}\cdot (-1)-\binom{N}{(n-1)/2}(-4)^{N-(n-1)/2}(-1)\pmod n\\\\&\equiv -\frac{n+1}{2}\cdot (-4)\cdot (-1)\equiv -2\pmod n\end{align}$$ It follows from $\gcd(n,2)=1$ that $$\sum_{k=0}^{n-1}2T_{n-1}\left(\frac k2\right)\equiv -1\pmod n$$