Let $F$ be an integral domain with characteristic $2$. Let $a\in F[t]$ and $a \notin F$. Let $\alpha (a)$ be a root of the equation $x^2+ax+1=0$. We define two sequences $X_m(a), Y_m(a) \in F[t], m \in \mathbb{Z}$ as follows: $$X_m(a)+\alpha (a)Y_m(a)=(\alpha (a))^m=(a+\alpha (a))^{-m}$$
Lemma. Let $F$ be an integral domain with characteristic $p=2$. Let $a \in F[t], a \notin F$. $X_m(a)$ (resp. $Y_m(a)$) is equal to the polynomial that we obtain if we substitute $t$ with $a$ at $X_m(t)$ (resp. $Y_m(t)$).
The degree of the polynomial $X_m(t)$ is $m-2$, if $m \geq 2$.
The degree of the polynomial $Y_m(t)$ is $m-1$, if $m \geq 2$.
$X_{-m}=X_m(a)+aY_m(a)$
$Y_{-m}(a)=Y_m(a)$
To prove this lemma I have done the following:
For the first two sentences about the degree I used induction on $m$. Is this correct?
As for the last two relations:
$$X_{-m}(a)+\alpha (a)Y_{-m}(a)=(a+\alpha (a))^m=X_m(a)+(a+\alpha (a))Y_m(a)\\ =X_m(a)+aY_m(a)+\alpha (a)Y_m(a) \\ \Rightarrow X_{-m}(a)=X_m(a)+aY_m(a)\ \ , \ \ Y_{-m}(a)=Y_m(a)$$
Is this correct?
$$$$
The induction for the first two sentences about the degree is the following:
Base case: For $m=2$ we have $X_2(a)+\alpha (a)Y_2(a)=(\alpha (a))^2=a\alpha (a)+1$. So $X_2(a)=1, Y_2(a)=a$. That means that $\text{deg}(X_2)=0=2-2$ and $\text{deg}(Y_2)=1=2-1$.
Inductive hypothesis: We suppose that it holds for $m=k$, i.e., $\text{deg}(X_k)=k-2$ and $\text{deg}(Y_k)=k-1$.
Inductive step: We will show that it holds for $n=k+1$, i.e., $\text{deg}(X_{k+1})=k-1$ and $\text{deg}(Y_{k+1})=k$. $$X_{k+1}+\alpha (a)Y_{k+1}=(a+\alpha (a))^{-(k+1)}=(a+\alpha (a))^{-k}(a+\alpha (a))^{-1} \\ =(X_k+\alpha (a)Y_k)(a+\alpha (a))^{-1}=(X_k+\alpha (a)Y_k)\alpha (a) \\ =\alpha (a)X_k+\alpha (a)^2Y_k=\alpha (a)X_k+(a\alpha (a)+1)Y_k \\ =Y_k+\alpha (a)[X_k+aY_k] \\ \Rightarrow X_{k+1}=Y_k \ \ , \ \ Y_{k+1}=X_k+aY_k \\ \text{ So we have that } \\ \text{deg}(X_{k+1})=\text{deg}(Y_k)=k-1 \\ \text{ and } \\ \text{deg}(Y_{k+1})=\max \{\text{deg}(X_k), \text{deg}(aY_k)\}=\max \{k-2, 1+k-1\}=k$$
Is this correct?
I don't think that your proof for the last statement is complete. It remains to justify why the identity $(a+\alpha (a))^m=X_m(a)+(a+\alpha (a))Y_m(a)$ holds ? I will suppose that you have an answer to this question because you used it ! (If you don't let me know). The other two statements can be proved by induction, but first let's make the formulation of the problem very clear . Here is my understanding of your question :
So from here I will assume that you proved the first statement, for the other statements we use induction.
First let's compute the first terms of the sequences $X_m$ and $Y_m$, using the fact that $\alpha(a)^2=a\alpha(a)+1$ $$X_2(a)=1 \text{ and } Y_2(a)=a $$
The only thing to remember here is : $$\left\{\begin{matrix} \deg(X_2)& = & 0\\ \deg(Y_2)& = & 1 \end{matrix}\right. \tag 1 $$
Now we can observe that the computation of the following terms can be done by induction : $$X_{m+1}+\alpha(a)Y_{m+1} = \alpha(a)(X_m+\alpha(a)Y_m)=Y_m+(aY_m+X_m)\alpha(a)$$ which gives you that $X_{m+1}=Y_m$ and $Y_{m+1}=aY_m+X_m$. if we pass to the degrees we obtain (assuming that $\deg(Y_m)\geq \deg(X_m)$ which can be proved by induction): $$\left\{\begin{matrix} \deg(X_{m+1})& = & \deg(Y_m)\\ \deg(Y_{m+1})& = & \deg(Y_m)+1 \end{matrix}\right. \tag 2 $$
You can know produce a rigorous proof by induction of the statements $\deg(X_m)=m-2$ and $\deg(Y_m)=m-1$ for $m\geq 2$ using the assertion $(1)$ in the basis steps and the assertion $(2)$ in the induction step.
If you have any questions just ask.