# To what is $X_{-m}+\alpha (a)Y_{-m}$ equal?

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?

• Your notations are very confusing. What's $X_{-m}$ ? Commented Sep 25, 2015 at 13:01
• The sequences of polynomials $X_m$ and $Y_m$ are defined as followed: $$X_m(a)+\alpha (a)Y_m(a)=(\alpha (a))^m=(a+\alpha (a))^{-m}$$ So $X_{-m}$ and $Y_{-m}$ are defined as above when we take $-m$ instead of $m$. @mercio Commented Sep 25, 2015 at 13:06
• I don't understand if it is $X_m(a)$ or $X_m$ who is in $F[t]$ Commented Sep 25, 2015 at 13:07
• $X_m(a)$ is a polynomial of $a$. @mercio Commented Sep 25, 2015 at 13:08
• But $a$ is not an indeterminate and you said in the question that $X_m(a)$ was an element of $F[t]$ Commented Sep 25, 2015 at 13:09

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 :

Question. Let $F$ be an integral domain with characteristic $p=2$. Let $a \in F[t], a \notin F$. Let $\alpha (a)$ be a root of the equation $x^2+ax+1=0$. There exits two unique polynomials $X_m(a), Y_m(a) \in F[t], m \in \mathbb{Z}$ such that: $$X_m(a)+\alpha (a)Y_m(a)=(\alpha (a))^m=(a+\alpha (a))^{-m}$$ prove that :

• For every $m\in \mathbb Z$ we have $X_{-m}=X_m(a)+aY_m(a)\quad Y_{-m}(a)=Y_m(a)$
• For every $m\in \mathbb Z$,If $m \geq 2$, then $\deg(X_{m})=m-2$ .
• For every $m\in \mathbb Z$,If $m \geq 2$ then $\deg(Y_{m})=m-1$.

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.

• @MaryStar As you have some problems in formulating question, I advise you to improve this point Commented Sep 26, 2015 at 18:28
• I added the induction I tried in my initial post... Could you take a look at it and tell me if the formulation is correct?  How can we prove that the equality $(a+\alpha (a))^m=X_m(a)+(a+\alpha (a))Y_m(a)$ holds? I thought that since $X_m(a)+\alpha (a)Y_m(a)=(\alpha (a))^m$ we can replace $\alpha (a)$ with $a+\alpha (a)$. Commented Sep 27, 2015 at 0:01
• Yes, your new proof is perfect, we can replace $\alpha(a)$ with $a+\alpha(a)$ because the definition of $X_m$ and $Y_m$ depend only in the equation $x^2+ax+1$ and $\alpha(a),a+\alpha(a)$ are both the roots of this equation which means that the equation $X_m+\alpha(a)Y_m=(\alpha(a))^m$ holds for any root $\alpha(a)$ of $x^2+ax+1$ so if we replace $\alpha(a)$ by $a+\alpha(a)$ it 's true also. This argument is subtle but you have to understand it and it's worth to included it in the proof. Second method : you can prove the two identities also by induction on $m>0$ Commented Sep 27, 2015 at 0:22
• So can we formulate the proof of the last two relations as follows?  For each root $z$ of the equation $x^2+ax+1=0$ it holds $$X_m(a)+zY_m(a)=z^m$$ One root is $z=\alpha (a)$. From the formulas of Vieta we have that the second root is $z=a+\alpha (a)$. Therefore we have $$X_m(a)+(a+\alpha (a))Y_m(a)=(a+\alpha (a))^m.$$ So, $$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).$$ Commented Sep 27, 2015 at 12:43
• Yes that's perfect Commented Sep 27, 2015 at 17:03