I Resolve the Recursion of Dickson polynomials

pawlo392
Messages
7
Reaction score
0
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.
 
Last edited:
Physics news on Phys.org
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 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 <br /> 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.
 
Back
Top