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:
$$D_{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}$$
Now, I am stuck here and not sure how to proceed.