Resolve the Recursion of Dickson polynomials

[pawlo392]

I am trying to prove the expression for Dickson polynomials:

$$D_n(x, a)=\sum_{i=0}^{\lfloor \frac{n}{2}\rfloor}d_{n,i}x^{n-2i}, \quad \text{where} \quad d_{n,i}=\frac{n}{n-i}{n-i\choose i}(-a)^i$$

I am supposed to use the recurrence relation:

$$D_n(x,a)=xD_{n-1}(x,a)-aD_{n-2}(x,a)$$

I have tried to use induction to prove this, but I am having trouble. Here's what I have so far:

Base case: For $n=1$, we have:

$$D_1(x,a)=x$$

which matches the expression for $D_n(x,a)$ when $n=1$. So the base case holds.

Inductive step: Assume that the expression for $D_n(x,a)$ holds for some $n \geq 1$. We want to show that it also holds for $n+1$.

From the recurrence relation, we have:

$$D_{n+1}(x,a) = xD_n(x,a) - aD_{n-1}(x,a)$$

Substituting the expression for $D_n(x,a)$ and $D_{n-1}(x,a)$, we get:

\begin{align*}
D_{n+1}(x,a) &= xD_n(x,a) - aD_{n-1}(x,a) \\
&= x\sum_{i=0}^{\lfloor \frac{n}{2}\rfloor}d_{n,i}x^{n-2i} - a\sum_{i=0}^{\lfloor \frac{n-1}{2}\rfloor}d_{n-1,i}x^{n-1-2i} \\
&= \sum_{i=0}^{\lfloor \frac{n}{2}\rfloor}d_{n,i}x^{n-2i+1} - \sum_{i=0}^{\lfloor \frac{n-1}{2}\rfloor}d_{n-1,i}ax^{n-1-2i} \\
&= \sum_{i=0}^{\lfloor \frac{n}{2}\rfloor}d_{n,i}x^{n-2i+1} - \sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}d_{n,i-1}ax^{n-2i+1} \\
\end{align*}

Now, I am stuck here and not sure how to proceed. Can someone please provide some guidance or hints on how to continue with the proof? Thanks in advance.

 

[pasmith]

I am trying to prove the expression for Dickson polynomials:

$$D_n(x, a)=\sum_{i=0}^{\lfloor \frac{n}{2}\rfloor}d_{n,i}x^{n-2i}, \quad \text{where} \quad d_{n,i}=\frac{n}{n-i}{n-i\choose i}(-a)^i$$

I am supposed to use the recurrence relation:

$$D_n(x,a)=xD_{n-1}(x,a)-aD_{n-2}(x,a)$$

If you do use induction, then your base case is to show that the result holds for $n = 0$ and $n = 1$, and your inductive hypothesis is that if the result holds for $n$ and $n-1$ then it holds also for $n + 1$. That will invole some manipulation of binomial coefficient identities.

However, there may be an easier way. The recurrence $$D_n(x,a) = xD_{n-1}(x,a) - aD_{n-2}(x,a)$$ subject to $$D_0(x,a) = 2, \qquad D_1(x,a) = x$$ is a constant coefficient linear recurrence for $D_n(x,a)$ in terms of $n$. It is straightforward to solve this recurrence and show directly that the resulting expression for $D_n(x,a)$ is of the required form.