A general summation of powers of roots of $x^2-x+q=0$ If $\alpha,\beta$  are the roots of the equation $x^2-x+q=0$ and $S_r=\alpha ^r + \beta ^r$, find $S_n$ in terms of $\sum a_iS_{n-i}$, where $a_i$ are constant terms for each $S_{n-1}$.
I tried to observe a pattern in the $S_r$:
$S_1=1, S_2=1-2q, S_3=1-3q,S_4=1-4q(1-2q)+6q^2$
I looked up for Vietta's theorem as well, did not work.
 A: Note that the roots satisfy $x^2 = x - q$. In particular, they satisfy $$x^n = x^{n-1} - qx^{n-2}$$
for $n \ge 2$. In matrix form, we may write this as $$\begin{bmatrix}\alpha^n \\ \alpha^{n-1} \end{bmatrix} = \begin{bmatrix} 1 & -q \\ 1 & 0 \end{bmatrix}\begin{bmatrix} \alpha^{n-1} \\ \alpha^{n-2}\end{bmatrix}; \quad n \ge 2.$$
Inductively, we get
$$\begin{bmatrix}\alpha^n \\ \alpha^{n-1} \end{bmatrix} = \begin{bmatrix} 1 & -q \\ 1 & 0 \end{bmatrix}^{n-1}\begin{bmatrix} \alpha \\ 1\end{bmatrix}; \quad n \ge 2.$$
And similarly, we have the same for $\beta$. Adding the similar equation for $\beta$ to the above equation gives us
$$\begin{bmatrix}S_n \\ S_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & -q \\ 1 & 0 \end{bmatrix}^{n-1}\begin{bmatrix} 1 \\ 2\end{bmatrix}; \quad n \ge 2.$$
Thus, we have
$$[S_n] = \begin{bmatrix} 1 & 0\end{bmatrix}\begin{bmatrix} 1 & -q \\ 1 & 0 \end{bmatrix}^{n-1}\begin{bmatrix} 1 \\ 2\end{bmatrix}; \quad n \ge 2.$$
This is a "closed form" for a lenient enough definition. If you are not satisfied, you can do better by diagonalising (if $\alpha \neq \beta$) the above matrix and getting a better form for it.
(However, that will not be particularly helpful since it would involve $\alpha^n$ and $\beta^n$.)
A: If $a,b$ are roots of $$x^2-x+q=0$$ then we have
$a^n(a^2-a+q)=0$ and  $b^n(b^2-b+q)=0$
, adding them and by defining
$S_n=a^n+b^n$, we get
$$S_{n+2}=S_{n+1}-qS_n \implies S_n=S_{n-1}-qS_n$$
Using the last result we can write $S_n$ in terms of $S_{n-1},~S_{n-2},~S_{n-3},....,S_0$ easily.
