Can you prove or disprove the following claim:
Let $S_k=2S_{k-1}-3S_{k-2}+2S_{k-3}$ with $S_0=0$ , $S_1=1$ , $S_2=1$ . Let $n$ be an odd natural number greater than $2$. Let $\left(\frac{D}{n}\right)$ be the Jacobi symbol where $D$ represents the discriminant of the characteristic polynomial $x^3-2x^2+3x-2$, and let $\delta(n)=n-\left(\frac{D}{n}\right)$ , then:
$$\text{If } n \text{ is a prime then } S_{\delta(n)} \equiv 0 \pmod{n}$$
You can run this test here. Note that $D=-28$ .
I have verified this claim for all $n$ up to $200000$ . I was searching for counterexample using the following PARI/GP code:
rec(m,P,Q,R)={s0=0;s1=1;s2=1;l=3;while(l<=m,s=P*s2+Q*s1+R*s0;s0=s1;s1=s2;s2=s;l++);return(s);}
RPT(n1,n2)={forprime(n=n1,n2,d=n-kronecker(-28,n);if(Mod(rec(d,2,-3,2),n)!=0,print(n);break))}
P.S.
Wolfram Alpha gives the following closed form for $S_k$ : $$S_k=\frac{i2^{-k} \cdot \left(\left(1-i\sqrt{7}\right)^k-\left(1+i\sqrt{7}\right)^k\right)}{\sqrt{7}}$$
Best Answer
The claim is true.
Proof :
Since the roots of $x^3-2x^2+3x-2=0$ are $x=1,\frac{1\pm i\sqrt 7}{2}$, there exist $A,B,C$ such that $$S_k=A\bigg(\frac{1-i\sqrt 7}{2}\bigg)^k+B\bigg(\frac{1+i\sqrt 7}{2}\bigg)^k+C\cdot 1^k$$ Using $S_0=0,S_1=S_2=1$, we get $A=\frac{i}{\sqrt 7}, B=\frac{-i}{\sqrt 7}$ and $C=0$ to have $$S_k=\frac{i}{\sqrt 7}\bigg(\frac{1-i\sqrt 7}{2}\bigg)^k-\frac{i}{\sqrt 7}\bigg(\frac{1+i\sqrt 7}{2}\bigg)^k\tag1$$
Case 1 : $n=7$
Since $\left(\frac{-28}{7}\right)=0$, we get $$S_{\delta(7)}=S_7=7\equiv 0\pmod 7$$
Case 2 : $n$ is a prime satisfying either $n\equiv 1,2$ or $4\pmod 7$
Since $\left(\frac n7\right)=1$, we get $$\bigg(\frac{-28}{n}\bigg)=\bigg(\frac{-1}{n}\bigg)\bigg(\frac{2^2}{n}\bigg)\bigg(\frac 7n\bigg)=(-1)^{(n-1)/2}\cdot 1\cdot \frac{(-1)^{3(n-1)/2}}{\left(\frac n7\right)}=1$$So, we have, using $(1)$, $$\begin{align}2^{n+2}S_{\delta(n)}&=2^{n+2}S_{n-1} \\\\&=\frac{i}{\sqrt 7}\bigg((1+i\sqrt 7)\left(1-i\sqrt{7}\right)^{n}-(1-i\sqrt 7)\left(1+i\sqrt{7}\right)^{n}\bigg) \\\\&=-\frac{i}{\sqrt 7}\bigg((1+i\sqrt 7)^n-(1-i\sqrt 7)^n\bigg)-\bigg((1+i\sqrt 7)^n+(1-i\sqrt 7)^n\bigg) \\\\&=-\frac{i}{\sqrt 7}\sum_{j=0}^{n}\binom nj\bigg((i\sqrt 7)^j-(-i\sqrt 7)^j\bigg)-\sum_{j=0}^{n}\binom nj\bigg((i\sqrt 7)^j+(-i\sqrt 7)^j\bigg) \\\\&=\sum_{k=1}^{(n+1)/2}\binom n{2k-1}2(-1)^{k+1}7^{k-1}+\sum_{k=0}^{(n-1)/2}\binom n{2k}2(-1)^{k+1}7^k\end{align}$$ Since $\binom{n}{m}\equiv 0\pmod n$ for $1\le m\le n-1$, we have $$\begin{align}2^{n+2}S_{\delta(n)}&\equiv 2(-1)^{(n+3)/2}7^{(n-1)/2}-2\pmod n \\\\&\equiv 2(-1)^{(n+3)/2}\frac{(-1)^{3(n-1)/2}}{\left(\frac n7\right)}-2\pmod n \\\\&\equiv 2(-1)^{2n}-2\pmod n \\\\&\equiv 0\pmod n\end{align}$$from which we get $$2^{n+2}S_{\delta(n)}\equiv 0\pmod n$$It follows from $\gcd(2^{n+2},n)=1$ that $$S_{\delta(n)}\equiv 0\pmod n$$
Case 3 : $n$ is a prime satisfying either $n\equiv 3,5$ or $6\pmod 7$
Since $\left(\frac n7\right)=-1$, we get $$\bigg(\frac{-28}{n}\bigg)=\bigg(\frac{-1}{n}\bigg)\bigg(\frac{2^2}{n}\bigg)\bigg(\frac 7n\bigg)=(-1)^{(n-1)/2}\cdot 1\cdot \frac{(-1)^{3(n-1)/2}}{\left(\frac n7\right)}=-1$$So, we have, using $(1)$, $$\begin{align}2^{n+1}S_{\delta(n)}&=2^{n+1}S_{n+1} \\\\&=\frac{i}{\sqrt 7} \bigg((1-i\sqrt 7)\left(1-i\sqrt{7}\right)^{n}-(1+i\sqrt 7)\left(1+i\sqrt{7}\right)^{n}\bigg) \\\\&=-\frac{i}{\sqrt 7}\bigg((1+i\sqrt 7)^n-(1-i\sqrt 7)^n\bigg)+\bigg((1+i\sqrt 7)^n+(1-i\sqrt 7)^n\bigg) \\\\&=-\frac{i}{\sqrt 7}\sum_{j=0}^{n}\binom nj\bigg((i\sqrt 7)^j-(-i\sqrt 7)^j\bigg)+\sum_{j=0}^{n}\binom nj\bigg((i\sqrt 7)^j+(-i\sqrt 7)^j\bigg) \\\\&=\sum_{k=1}^{(n+1)/2}\binom{n}{2k-1}2(-1)^{k+1}7^{k-1}+\sum_{k=0}^{(n-1)/2}\binom{n}{2k}2(-1)^{k}7^k \\\\&\equiv 2(-1)^{(n+3)/2}7^{(n-1)/2}+2\pmod n \\\\&\equiv 2(-1)^{(n+3)/2}\frac{(-1)^{3(n-1)/2}}{\left(\frac n7\right)}+2\pmod n \\\\&\equiv 2(-1)^{2n+1}+2\pmod n \\\\&\equiv 0\pmod n\end{align}$$from which we get $$2^{n+1}S_{\delta(n)}\equiv 0\pmod n$$It follows from $\gcd(2^{n+1},n)=1$ that $$S_{\delta(n)}\equiv 0\pmod n$$
From the three cases above, the claim follows.$\quad\blacksquare$