Given matrix $$ A=\begin{bmatrix} x+y&xy&0& .&.&. &0\\ 1&x+y&xy&0& .&.&0 \\ 0&1&x+y&xy&.&.&. \\ .&.&.&.&.&.&. \\ .&.&.&.&.&.&0 \\ .&.&.&.&.&.&xy \\ 0&.&.&.&0&1&x+y \end{bmatrix} $$

prove by induction that $$|A|=\frac{x^{n+1}-y^{n+1}}{x-y}$$ $x \neq y$, $A_{n \times n}$.

The determinant expression appears to be Dickson polynomial of second kind.

Let $D_n$ be the determinant of $A_n$. We can see that the appropriate recurrence relation is $$D_n=(x+y)D_{n-1}-xyD_{n-2}$$

Base cases: $$D_1=x+y=\frac{x^2-y^2}{x-y}$$

$$ D_2=(x+y)^2-xy=x^2+xy+y^2=\frac{x^3-y^3}{x-y} $$

Suppose that $$D_n=(x+y)D_{n-1}-xyD_{n-2}$$ Then we need to prove that $$D_{n+1}=(x+y)D_{n}-xyD_{n-1}$$

Which can be developed as: $$ D_{n+1}=(x+y)((x+y)D_{n-1}-xyD_{n-2})-xyD_{n-1}= $$ $$ =(x+y)^2D_{n-1}-xy(x+y)D_{n-2}-xyD_{n-1}= $$ $$ =(x^2+xy+y^2)D_{n-1}-xy(x+y)D_{n-2}= $$ $$ =\frac{x^3-y^3}{x-y}D_{n-1}-xy(x+y)D_{n-2} $$

I tried doing this up to $D_{n-6}$ in order to get any insights into possible simplification but I'm pretty stuck.


Your base cases are good. For the induction step, assume that $$D_n=\frac{x^{n+1}-y^{n+1}}{x-y}\quad \text{and}\quad D_{n-1}=\frac{x^{n}-y^{n}}{x-y}.$$ Then you have that $$D_{n+1}=(x+y)D_n-xyD_{n-1},$$so you only have to show that $$(x+y)\frac{x^{n+1}-y^{n+1}}{x-y}-xy\frac{x^{n}-y^{n}}{x-y}=\frac{x^{n+2}-y^{n+2}}{x-y}.$$ Developping the LHS gives you \begin{align}(x+y)\frac{x^{n+1}-y^{n+1}}{x-y}-xy\frac{x^{n}-y^{n}}{x-y} & = \frac{x^{n+2}+x^{n+1}y-xy^{n+1}-y^{n+2}-x^{n+1}y+xy^{n+1}}{x-y}\\ & = \frac{x^{n+2}-y^{n+2}}{x-y}.\end{align}


A linear algebra approach to the recurrence relation is to write it in matrix form: $$\mathcal{D}_n\equiv \begin{pmatrix} D_{n} \\ D_{n-1}\end{pmatrix}=\begin{pmatrix} x+y & -xy\\1 & 0 \end{pmatrix}\begin{pmatrix} D_{n-1} \\ D_{n-2}\end{pmatrix}\equiv M \mathcal{D}_{n-1},\hspace{4mm} \mathcal{D}_0 = \binom{1}{0}.$$ (I choose $D_0=1,D_{-1}=0$ so that the recurrence for $D_n$ in terms of $D_{n-1},D_{n-2}$ valid for $n\geq 1$.) Then $D_n=(\mathcal{D}_n)_1=(M^n \mathcal{D}_0)_1=(M^n)_{11},$ so computing $D_n$ amounts to matrix multiplication. But the eigenvalues and eigenvectors are simple enough in this case, yielding the spectral decomposition $$M=\Lambda D \Lambda^{-1}=\begin{pmatrix}x & y \\ 1 & 1\end{pmatrix}\begin{pmatrix}x & 0 \\ 0 & y\end{pmatrix}\begin{pmatrix}x & y \\ 1 & 1\end{pmatrix}^{-1}$$ and therefore \begin{align} M^n &=(\Lambda D \Lambda^{-1})^n \\ &= \Lambda D^n \Lambda^{-1} \\ &= \begin{pmatrix}x & y \\ 1 & 1\end{pmatrix}\begin{pmatrix}x^n & 0 \\ 0 & y^n\end{pmatrix}\begin{pmatrix}x & y \\ 1 & 1\end{pmatrix}^{-1} \\ &= \begin{pmatrix}x^{n+1} & y^{n+1} \\ x^n & y^n\end{pmatrix}\cdot \frac{1}{x-y}\begin{pmatrix}1 & -y \\ -1 & x\end{pmatrix}\\ &=\frac{1}{x-y}\begin{pmatrix}x^{n+1}-y^{n+1} & x y^{n+1}-x^{n+1}y \\ x^{n}-y^{n}& xy^{n}-yx^{n}\end{pmatrix}. \end{align} From the upper-left corner we read off the anticipated result.

  • $\begingroup$ Thanks for your version! I have to admit that we didn't learn eigenvalues yet but when we do I will certainly revisit this question. $\endgroup$ – Yos May 3 '17 at 7:14

You did the base cases $n=1,2$, then you do the inductive step using strong induction; suppose your claim is true for any $m \leq n$, then using the recursive formula, for $n \geq 3$: \begin{align} D_{n+1} &=(x+y)D_n-xyD_{n-1} =\\ &=(x+y)\frac{x^{n+1}-y^{n+1}}{x-y} -xy\frac{x^n-y^n}{x-y} = \\ &= \frac{1}{x-y}(x^{n+2}-xy^{n+1}+yx^{n+1}-y^{n+2}-x^{n+1}y+xy^{n+1})= \\ &= \frac{x^{n+2}-y^{n+2}}{x-y} \end{align} which proves the claim for $m=n+1$. By induction, the claim is true for any $n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.