Resolve the Recursion of Dickson polynomials

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.

pawlo392 said:

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 [itex]n = 0[/itex] and [itex]n = 1[/itex], and your inductive hypothesis is that if the result holds for [itex]n[/itex] and [itex]n-1[/itex] then it holds also for [itex]n + 1[/itex]. That will invole some manipulation of binomial coefficient identities.

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