A general summation of powers of roots of $x^2-x+q=0$

Question

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.

Answer 1

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$.)

Answer 2

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.