# Solving a recurrence relation with n squared

I have trouble solving the following recurrence:

$$a_{1}=1, a_{n}=a_{n-1}\cdot n^{2}$$ for $n>1$. It seems somewhat untypical to me, could you give me some general advice on dealing with such examples?

• What exactly do you want to do with this recurrence? – Anton Grudkin Jun 9 '16 at 17:53
• What does $a_n$ look like if you successively apply the recurrence relation? – Semiclassical Jun 9 '16 at 17:53
• Work out the first four or five terms of the progression by hand, and you will see a pattern (it is very simple). This is always the best place to start. Intuition can be confirmed by algebra, but algebra unconstrained by intuition wanders round in circles and goes nowhere. – Martin Kochanski Jun 9 '16 at 17:54
• Thank you @MartinKochanski for your informative suggestion and others for putting it brilliantly into practice. – Theta Jun 9 '16 at 18:53

$a_2=2^2$, $a_3= 2^23^2$. In general, $a_n = (n!)^2$.

You can check by induction - true for $n=1$. If true for $n$, $a_{n+1}= (n!)^2(n+1)^2 = ((n+1)!)^2$.

Alteratively to the excellent answer by @Vaneet, you can take the logarithm and define $\ln(a_n)=b_n$ to turn the product in a sum.

$$\ln(a_n)=\ln(a_{n-1})+2\ln(n),$$ or

$$b_n=b_{n-1}+2\ln(n).$$

With $b_0=0$, the solution of this classical recurrence is

$$b_n=2\sum_{k=1}^n\ln(k)$$ i.e.

$$a_n=\left(\prod_{k=1}^nk\right)^2.$$

\begin{align} a_n&=n^2 a_{n-1}\\ &=n^2(n-1)^2a_{n-2}\\ &=n^2(n-1)^2(n-2)^2a_{n-3}\\ &\vdots\\ &=n^2(n-1)^2(n-2)^2\cdots 2^2\overbrace{a_1}^{=1}\\ &=[n(n-1)(n-2)\cdots 2\cdot 1]^2\\ &=(n!)^2\qquad\blacksquare\end{align}