How to prove that the recurrence $a_{n}=a_{n-1}+n^2a_{n-2}$ gives $(n+1)!$ without induction

Question

Define the sequence $\{a_n\}$ by $a_{1}=2,a_{2}=6$, and for $n>2$, $$a_{n}=a_{n-1}+n^2a_{n-2}$$

show that $$a_{n}=(n+1)!$$

I know if we use induction,it is easy to prove it. $$n!+n^2(n-1)!=n![1+n]=(n+1)!$$

But without using induction, can we prove this result?

Answer 1

Divide $$ a_n=a_{n-1}+n^2 a_{n-2} $$ by $a_{n-1}$: $$ \frac{a_n}{a_{n-1}}=1+n^2\frac{a_{n-2}}{a_{n-1}} $$ Let $x_n=\frac{a_n}{a_{n-1}}$; so, $$ x_n=1+\frac{n^2}{x_{n-1}}. $$ $x_n=n+1$ is a solution of it: $$ n+1=1+\frac{n^2}{(n-1)+1}. $$ So, $a_n/a_{n-1}=n+1$ and $a_n=C(n+1)!$. $a_1=2\Longrightarrow C=1$.

Answer 2

Consider the sequence $a_{1}=2,a_{2}=6$, $a_{n}=a_{n-1}+n^2a_{n-2}$. Let $a_{n} = \Gamma(n+2) \, b_{n}$ for which it is seen that: \begin{align} \Gamma(n+2) \, b_{n} = \Gamma(n+1) \, b_{n-1} + n \, \Gamma(n+1) \, b_{n} \end{align} or \begin{align} (n+1) \, b_{n} = b_{n-1} + n \, b_{n-2} \end{align} where $b_{1} = b_{2} = 1$. By calculating the next set of terms it is quickly realized that $b_{n} = 1$ for $n \geq 1$. Utilizing this result it is determined that the solution to $a_{n}=a_{n-1}+n^2a_{n-2}$ is $a_{n} = \Gamma(n+2)$.

Answer 3

Well, if we know that the solution to $a_{n}=a_{n-1}+n^2a_{n-2} $ is $a_n =(n+1)! $, let's let $a_n =(n+1)!b_n $ (with initial values $b_1 = b_2 = 1$ and see what happens.

$(n+1)!b_n =n!b_{n-1}+n^2(n-1)!b_{n-2} =n!b_{n-1}+nn!b_{n-2} $ or $(n+1)b_n =b_{n-1}+nb_{n-2} $.

And for this, we see that $b_n = 1$ is the solution.

Note that from $(n+1)b_n =b_{n-1}+nb_{n-2} $, $(n+1)b_n-(n+1)b_{n-1} =-nb_{n-1}+nb_{n-2} $ or $(n+1)(b_n-b_{n-1}) =-n(b_{n-1}-b_{n-2}) $. Since $b_1 = b_2 = 1$, this implies that $b_n = 1$ for all $n$.