Leicich wrote: Let $\alpha$ and $\beta$ be the roots of $x^{2} - qx + 1$, where $q$ is a rational number larger than $2$. Let $s_1 = \alpha + \beta$, $t_1 = 1$, and for all integers $n \geq 2$: $s_n = \alpha^n + \beta^n$ $t_n = s_{n-1} + 2s_{n-2} + \cdot \cdot \cdot + (n - 1)s_{1} + n$ Prove that, for all odd integers $n$, $t_n$ is the square of a rational number. Note that $S_0=2$ and $S_1=q$ and $S_{n+2}=qS_{n+1}-S_n$ and so $S_n\in\mathbb Q$ $\forall n$ Then : $\sum_{k=0}^n\alpha^{n-k}x^k=\frac{x^{n+1}-\alpha^{n+1}}{x-\alpha}$ Taking the derivative, this gives $\sum_{k=1}^nk\alpha^{n-k}x^{k-1}=\frac{(n+1)x^n(x-\alpha)-x^{n+1}+\alpha}{(x-\alpha)^2}$ Setting there $x=1$ (note that $q>2$ implies $\alpha>1$), we get $\sum_{k=1}^nk\alpha^{n-k}=\frac{(n+1)(1-\alpha)-1+\alpha^{n+1}}{(1-\alpha)^2}$ $=\frac{n-(n+1)\alpha+\alpha^{n+1}}{\alpha^2+1-2\alpha}$ $=\frac{n\beta-n-1+\alpha^{n}}{\alpha+\beta-2}$ So $t_n=\sum_{k=1}^nk\alpha^{n-k}+\sum_{k=1}^nk\beta^{n-k}-n$ $=\frac{n\beta-n-1+\alpha^{n}}{\alpha+\beta-2}$ $+\frac{n\alpha-n-1+\beta^{n}}{\alpha+\beta-2}-n$ $=\frac{\alpha^n+\beta^n-2}{\alpha+\beta-2}$ So $t_n=\left(\frac{\alpha^{\frac n2}-\beta^{\frac n2}}{\sqrt\alpha-\sqrt\beta}\right)^2$ So $\sqrt{t_{2n+1}}=\left|\frac{\alpha^n\sqrt\alpha-\beta^n\sqrt\beta}{\sqrt\alpha-\sqrt\beta}\right|$ $=\left|\frac{\alpha^{2n+1}-1}{\alpha^n(\alpha -1)}\right|$ $=\frac{\sum_{k=0}^{2n}\alpha^k}{\alpha^n}$ $=1+\sum_{k=1}^nS_k$ And this last expression is obviously a rational number. Q.E.D.

Another proof that $t_n=\frac{\alpha^n+\beta^n-2}{\alpha+\beta-2}$. We have $\alpha\beta=1,s_1=\alpha+\beta=q,s_2=q^2-2.\quad(*_0)$ With $s_0=2$ we have \begin{align*}s_{n+2}=\alpha^{n+2}+\beta^{n+2}=(\alpha^{n+1}+\beta^{n+1})(\alpha+\beta)-\alpha\beta(\alpha^n+\beta^n)=qs_{n+1}-s_n\quad(*_1)\end{align*} We have \begin{align*} t_{n+1}&=s_n+2s_{n-1}+\cdots+ns_1+n+1\\ &=(s_{n-1}+2s_{n-2}+\cdots+(n-1)s_1+n)+s_n+\cdots+s_1+1\\ &=t_n+s_n+\cdots+s_1+1\\ \Rightarrow\quad&\boxed{t_{n+1}-t_n=s_n+s_{n-1}+\cdots+s_1+1}\quad(*_2) \end{align*}Plugging in $n+1$ for $n$ we get... \begin{align*} t_{n+2}-t_{n+1} &=s_{n+1}+\cdots+s_2+s_1+1\\ &\stackrel{*_1}{=}(qs_n-s_{n-1})+(qs_{n-1}-s_{n-2})+\cdots+(qs_2-s_1)+s_2+s_1+1\\ &=s_n+(q-1)(s_n+s_{n-1}+\cdots+s_1+1)-(q-1)s_1-(q-1)+s_2+1\\ &\stackrel{*_2}{=}s_n+(q-1)(t_{n+1}-t_n)-(q-1)q-(q-1)+(q^2-2)+1\\ \Rightarrow\quad&\boxed{t_{n+2}-t_{n+1}=s_n+(q-1)(t_{n+1}-t_n)}\quad(*_3) \end{align*}Summing $*_3$ through $n\in\{n,n-1,...,1\}$ we get a telescopic sum that yields \begin{align*} t_{n+2}-t_2 &=(s_n+s_{n-1}+\cdots+s_1)+(q-1)(t_{n+1}-t_1)\\ &=(t_{n+1}-t_n-1)+(q-1)(t_{n+1}-1)\\ &=qt_{n+1}-t_n-t_2+2\\ \Rightarrow\quad&\boxed{t_{n+2}-t_{n+1}=(q-1)t_{n+1}-t_n+2} \end{align*}Going back to $*_3$ gives $-t_n+2=s_n-(q-1)t_n\Leftrightarrow t_n=\frac{s_n-2}{q-2}=\frac{\alpha^n+\beta^n-2}{\alpha+\beta-2}$.