- Let $$a_n=2^n\left[\cos^n\left(\dfrac{2\pi}{9}\right)+\cos^n\left(\dfrac{4\pi}{9}\right)+\cos^n\left(\dfrac{8\pi}{9}\right)\right].$$ Show that $a_n\in\mathbb{Z}$ for all $n\in\mathbb{Z}$.
- Find the last digit of $a_{10^6}$.
My progress:
I believe it can be solved by expressing $a_n$ as a linear recurrence by using the cubic equation $x^3-3x+1=0$ which has the roots $x_1=2\cos\left(\dfrac{2\pi}{9}\right)$, $x_2=2\cos\left(\dfrac{4\pi}{9}\right)$, $x_3=2\cos\left(\dfrac{8\pi}{9}\right)$. I'm just not really sure how to connect $a_n$ to this cubic equation.
I guess that if you could find a linear recurrence to $a_n$, the last digit would be cyclic and could be found that way. I was hoping to solve it without using computer work, but maybe that's tough.
As shown in $(10)$ below, $x_1=2\cos\left(\frac{2\pi}{9}\right)$, $x_2=2\cos\left(\frac{4\pi}{9}\right)$, and $x_3=2\cos\left(\frac{8\pi}{9}\right)$ all satisfy $$ x^3-3x+1=0\tag{1} $$ As shown in $(13)$ below, the sequence $a_n=c_1x_1^n+c_2x_2^n+c_3x_3^n$ satisfies $$ \begin{align} a_n&=3a_{n-2}-a_{n-3} \end{align}\tag{2} $$ Furthermore, $$ \begin{align} x_1&=e^{2\pi i/9}+e^{-2\pi i/9}\\ x_2&=e^{4\pi i/9}+e^{-4\pi i/9}\\ x_3&=e^{8\pi i/9}+e^{-8\pi i/9} \end{align}\tag{3} $$ Thus, as shown in $(7)$ below, being the sum of the ninth roots of unity minus the sum of the third roots of unity, $$ x_1+x_2+x_3=0\tag{4} $$ Using equation $(8)$ below, we get $$ x_1^2+x_2^2+x_3^2=6\tag{5} $$ Therefore, we get $$ \begin{align} a_0&=x_1^0+x_2^0+x_3^0=3\\ a_1&=x_1^1+x_2^1+x_3^1=0\\ a_2&=x_1^2+x_2^2+x_3^2=6 \end{align}\tag{6} $$ Eqations $(2)$ and $(6)$ show that $a_n\in\mathbb{Z}$ for all $n\ge0$.
Why $x_k$ Satisfies (1)
As noted above, the sum of $x_k$ is the difference of the sum of the ninth roots of unity and the sum of the third roots of unity, and therefore $0$. That is, $$ \begin{align} &x_1+x_2+x_3\\[6pt] &=\small\left(e^{2\pi i/9}+e^{16\pi i/9}\right)+\left(e^{4\pi i/9}+e^{14\pi i/9}\right)+\left(e^{8\pi i/9}+e^{10\pi i/9}\right)\\ &=\small\left(e^{0\pi i/9}+e^{2\pi i/9}+e^{4\pi i/9}+e^{6\pi i/9}+e^{8\pi i/9}+e^{10\pi i/9}+e^{12\pi i/9}+e^{14\pi i/9}+e^{16\pi i/9}\right)\\ &-\small\left(e^{0\pi i/9}+e^{6\pi i/9}+e^{12\pi i/9}\right)\\ &=0-0\tag{7} \end{align} $$
Squaring and subtracting $2$ yields $$ \begin{align} x_1^2-2=\left(e^{2\pi i/9}+e^{-2\pi i/9}\right)^2-2&=e^{4\pi i/9}+e^{-4\pi i/9}=x_2\\ x_2^2-2=\left(e^{4\pi i/9}+e^{-4\pi i/9}\right)^2-2&=e^{8\pi i/9}+e^{-8\pi i/9}=x_3\\ x_3^2-2=\left(e^{8\pi i/9}+e^{-8\pi i/9}\right)^2-2&=e^{2\pi i/9}+e^{-2\pi i/9}=x_1 \end{align}\tag{8} $$ Squaring each equation in $(8)$ and subtracting $2$ yields $$ \begin{align} x_1^4-4x_1^2+2&=x_2^2-2=x_3\\ x_2^4-4x_2^2+2&=x_3^2-2=x_1\\ x_3^4-4x_3^2+2&=x_1^2-2=x_2\\ \end{align}\tag{9} $$ Adding $(8)$, $(9)$, and $x_k=x_k$, we get (using subscripts mod $3$) $$ x_k^4-3x_k^2+x_k=\overbrace{(x_k^4-4x_k+2)}^{x_{k-1}\text{ from }(9)}+\overbrace{(x_k^2-2)}^{x_{k+1}\text{ from }(8)}+x_k=x_1+x_2+x_3=0\tag{10} $$
Since $x_k\ne0$, equation $(10)$ says that $x_k$ must satisfy $(1)$.
Why Do The Roots Of (1) Satisfy (2)
Any root of $x^3-3x+1=0$ also satisfies $$ x^n=3x^{n-2}-x^{n-3}\tag{11} $$ That is, $a_n=x^n$ satisfies $(2)$
Any linear combination of solutions to $(2)$ is also a solution to $(2)$. Thus, we get that $$ a_n=c_1x_1^n+c_2x_2^n+c_3x_3^n\tag{12} $$ is a solution of $(2)$ for any $c_k$. That is, $$ \begin{align} a_n &=c_1x_1^n+c_2x_2^n+c_3x_3^n\\ &=c_1(3x_1^{n-2}-x_1^{n-3})+c_2(3x_2^{n-2}-x_2^{n-3})+c_3(3x_3^{n-2}-x_3^{n-3})\\ &=3(c_1x_1^{n-2}+c_2x_2^{n-2}+c_3x_3^{n-2})-(c_1x_1^{n-3}+c_2x_2^{n-3}+c_3x_3^{n-3})\\ &=3a_{n-2}-a_{n-3}\tag{13} \end{align} $$
Last Digit of $a_{10^6}$
Brute force computation shows that mod $10$, $a_n$ has a period of $434$. Since $10^6\equiv64\pmod{434}$ and $a_{64}\equiv6\pmod{10}$, $a_{10^6}\equiv6\pmod{10}$. Since $a_{10^6}=x_1^{10^6}+x_2^{10^6}+x_3^{10^6}\ge0$, the last digit of $a_{10^6}$ is $6$.