# Recurrence relation by linear algebra.

Got stuck trying to solve this recurrence relation found over here using my favourite set of tools in linear algebra. Question, find analytic or algebraic expression for $a_n$: $$a_n = n a_{n-1} + n(n-1)a_{n-2}$$

So this question would be searching for a linear-algebraic method for finding a solution.

Own work so far

So I let $v_0$ be a start-vector containing the initial values and then the matrix : $$M_n = \left[\begin{array}{cc} n & n(n-1)\\1&0 \end{array}\right]$$ will take us one step forward in the recurrence by matrix-vector multiplication :$$v_1 = M_1v_0$$

A typical approach with linear algebra then would be to try to find a transformation to some basis which makes the $M_n$ do easily expressible things. Ideal case would be an eigenvalue basis which would give the solution as a linear combination of products or exponentials of the eigenvalues. However in this problem I get different eigenvalue spaces for each $n$.

One observation one can make is that $$(M_n) = Q_{n-1}M_{n-1}$$ for the quite nice difference-transformation $$Q_n = \left[\begin{array}{cc} \frac{n+2}{n}&-\frac{n+2}{n}\\ 0&1\end{array}\right] = \left[\begin{array}{cc} \frac{n+2}{n}&0\\0&1\end{array}\right] \left[\begin{array}{cc}1&-1\\0&1\end{array}\right]$$ or similarly multiplied from the "other side". What would be convenient is probably if we could "bake together" a right side multiplied Q and a left side multiplied $Q^{-1}$ so that the Q:s could multiply into the $M_{n-1}$ $T$ or $T^{-1}$ in the eigenvalue decomposition $M_{n-1} = TET^{-1}$. Like a "sequence" of equivalence relations between $M_{n}$ and $M_{n-1}$. Would this be possible to do (and if so, would it help us)?

Strange observation

It seems possible to find Q such that $$Q_nM_{n-1}Q_n = M_{n}$$ which is a matrix equivalence with $P = Q^{-1}$ I can find such using numeric optimization techniques but to me they don't make sense as I expect to find solutions to Q to this equation: $$Q_nM_{n-1}(Q_n)^{-1} = M_{n}$$ which would be an ordinary matrix similarity.

Does someone know how to interpret or use this?

• Thanks. I suppose me writing such a large hint would mostly mess up the other question, but at least I can link it in. – mathreadler Mar 16 '16 at 17:15
• Are you aware of math.stackexchange.com/q/1700319 ? – Jean Marie Mar 16 '16 at 17:39
• Yes thank you @JeanMarie I have linked it now in the start of the question so people can find it from here, and also should be able to find this question from it. – mathreadler Mar 16 '16 at 17:42