Lucas数列の関係式

$\alpha\beta=Q$ なので
$$ U_{-n} =\frac{\alpha^{-n}-\beta^{-n}}{\alpha-\beta} =\frac{\beta^n-\alpha^n}{Q^n(\alpha-\beta)} =-Q^{-n}U_n $$
であり、同様に $V_{-n}=Q^{-n}V_n$ である。
また $(\alpha-\beta)^2=D$ より
$$ V_n^2-DU_n^2 =(\alpha^n+\beta^n)^2-(\alpha^n-\beta^n)^2 =4(\alpha\beta)^n =4Q^n. $$
加法公式については、直接展開すると
$$ U_mV_n+U_nV_m =\frac{2\alpha^{m+n}-2\beta^{m+n}}{\alpha-\beta} =2U_{m+n} $$
を得る。また
$$ V_mV_n+DU_mU_n =(\alpha^m+\beta^m)(\alpha^n+\beta^n) +(\alpha^m-\beta^m)(\alpha^n-\beta^n) =2V_{m+n}. $$
加法公式で $n$ を $-n$ に置き、負添字公式を用いると
$$ 2U_{m-n} =Q^{-n}(U_mV_n-U_nV_m), $$
$$ 2V_{m-n} =Q^{-n}(V_mV_n-DU_mU_n) $$
となる。両辺に $Q^n$ を掛ければ差の公式を得る。

$A:=\alpha^r$、$B:=\beta^r$ とおくと
$$ A+B=V_r(P,Q),\qquad AB=Q^r. $$
従って $A,B$ は $X^2-V_r(P,Q)X+Q^r$ の根である。
$A\ne B$ の場合、Binet表示から
$$ U_n(V_r,Q^r)=\frac{A^n-B^n}{A-B}. $$
一方
$$ U_r(P,Q)=\frac{A-B}{\alpha-\beta} $$
だから、両式の積は
$$ \frac{A^n-B^n}{\alpha-\beta} =\frac{\alpha^{rn}-\beta^{rn}}{\alpha-\beta} =U_{rn}(P,Q) $$
である。また $V_n(V_r,Q^r)=A^n+B^n=V_{rn}(P,Q)$ である。
$A=B$ の場合は Binet 表示が使えないので、漸化式で示す。$S_n:=\sum_{j=0}^{n-1}A^{n-1-j}B^j$（$S_0=0$）とおくと、$A,B$ の多項式としての恒等式
$$ A^n-B^n=(A-B)S_n,\qquad S_{n+2}=(A+B)S_{n+1}-AB\,S_n $$
が成り立つ（2 つ目は、両辺の $A^{n+1-j}B^j$ の係数を比べると確かめられる。$0< j< n+1$ では右辺の係数が $1+1-1=1$、$j=0,n+1$ では $1$ である）。$S_0=0$、$S_1=1$ なので、$S_n$ は $U_n(A+B,AB)=U_n(V_r,Q^r)$ と同じ初期値と漸化式をもち、両者は一致する。したがって $U_{rn}(P,Q)=\dfrac{A^n-B^n}{\alpha-\beta}=\dfrac{A-B}{\alpha-\beta}S_n=U_r(P,Q)\,U_n(V_r,Q^r)$ である（この計算は $A\ne B$ でも成り立つ）。第2種については、$A^n+B^n$ と $V_n(A+B,AB)$ がともに初期値 $2$、$A+B$ と同じ漸化式をもつので一致する。$\blacksquare$

Binet表示を用いると
$$ \begin{aligned} D(U_{n+r}^2-Q^rU_n^2) &=(\alpha^{n+r}-\beta^{n+r})^2 -(\alpha\beta)^r(\alpha^n-\beta^n)^2\\ &=(\alpha^r-\beta^r)(\alpha^{2n+r}-\beta^{2n+r})\\ &=D\,U_rU_{2n+r}. \end{aligned} $$
$D\ne0$ なので割ることができ、1 つ目の式を得る。
同様に
$$ \begin{aligned} V_{n+r}^2-Q^rV_n^2 &=(\alpha^{n+r}+\beta^{n+r})^2 -(\alpha\beta)^r(\alpha^n+\beta^n)^2\\ &=(\alpha^r-\beta^r)(\alpha^{2n+r}-\beta^{2n+r})\\ &=DU_rU_{2n+r}, \end{aligned} $$
となり 2 つ目の式を得る。

正負の符号を同時に扱うため
$$ (\alpha^{nr}\pm\beta^{nr})^2 -(\alpha^{(n-1)r}\pm\beta^{(n-1)r}) (\alpha^{(n+1)r}\pm\beta^{(n+1)r}) $$
を展開する。同符号の純粋な冪は相殺し、結果は
$$ \mp Q^{(n-1)r}(\alpha^r-\beta^r)^2 =\mp DQ^{(n-1)r}U_r^2 $$
となる。負号を選んだ式を $D=(\alpha-\beta)^2$ で割れば 1 つ目の式を得て、正号を選べば 2 つ目の式を得る。

$n$ についての帰納法で示す。$n=1$ では $U_2=P$、$U_1=1$、$U_0=0$ なので右辺は $M$ に等しい。$n$ で成り立つとすると
$$ M^{n+1}=M^nM=\begin{pmatrix}U_{n+1}&-QU_n\\U_n&-QU_{n-1}\end{pmatrix}\begin{pmatrix}P&-Q\\1&0\end{pmatrix}=\begin{pmatrix}PU_{n+1}-QU_n&-QU_{n+1}\\PU_n-QU_{n-1}&-QU_n\end{pmatrix} $$
であり、漸化式 $U_{n+2}=PU_{n+1}-QU_n$、$U_{n+1}=PU_n-QU_{n-1}$ により $n+1$ の場合の形になる。
行列式は乗法的なので $\det M^n=(\det M)^n=Q^n$ である。一方、右辺の行列式は $-QU_{n+1}U_{n-1}+QU_n^2$ である。$Q\ne0$ なら両辺を $-Q$ で割って $U_{n+1}U_{n-1}-U_n^2=-Q^{n-1}$ を得る。$Q=0$ でも、両辺は $P,Q$ の多項式であり（$U_n$ は漸化式から $P,Q$ の整数係数多項式）、$Q\ne0$ のすべての点で一致するので、多項式として等しく、$Q=0$ でも成り立つ。
最後に $W_n:=U_{n+1}-QU_{n-1}$ とおくと、$W_1=P-0=P=V_1$、$W_2=U_3-QU_1=(P^2-Q)-Q=P^2-2Q=V_2$ であり、$W_n$ は $U$ の同じ漸化式を満たす 2 つの列の一次結合なので、同じ漸化式を満たす。よって $W_n=V_n$ である。跡は $U_{n+1}-QU_{n-1}$ そのものである。$\blacksquare$

整数性は初期値 $0,1,2,P$ が整数で、漸化式の係数 $P,-Q$ が整数であることから、$n$ についての帰納法で従う。
$V_n\equiv PU_n\pmod2$ も帰納法で示す。$n=0$ では $V_0=2\equiv0=PU_0$、$n=1$ では $V_1=P=PU_1$ である。$n,n+1$ で成り立てば
$$ V_{n+2}=PV_{n+1}-QV_n\equiv P\cdot PU_{n+1}-Q\cdot PU_n=PU_{n+2}\pmod 2 $$
である。
後半は定義から直接計算できる。$V_n+U_n(\alpha-\beta)=(\alpha^n+\beta^n)+(\alpha^n-\beta^n)=2\alpha^n$ であり、符号を変えれば $\beta^n$ の式を得る。$(\alpha-\beta)^2=D$ は冒頭で見た。$\blacksquare$