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?

  • $\begingroup$ Thanks. I suppose me writing such a large hint would mostly mess up the other question, but at least I can link it in. $\endgroup$ – mathreadler Mar 16 '16 at 17:15
  • $\begingroup$ Are you aware of math.stackexchange.com/q/1700319 ? $\endgroup$ – Jean Marie Mar 16 '16 at 17:39
  • $\begingroup$ 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. $\endgroup$ – mathreadler Mar 16 '16 at 17:42

Your Answer

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

Browse other questions tagged or ask your own question.