# How to solve this recurrence relation related to the Group theoritic problem?

I was trying to count the number of elements of order 2 in the group $S_n$ and somehow translated the problem to the following recurrence relation.

$a_{n+1} = a_n + na_{n-1}$ with the initial conditions $a_0=0, a_1=1, a_2=2$ for $n \geq 3$

I don't know how to proceed after this stage. Kindly help.

• Google for "linear recursion", or search on MSE - e.g., here. – Dietrich Burde Apr 19 '17 at 9:27
• Also the number of elements of order $2$ in $S_n$ have been determined on MSE. For a start, read this question, and this one. – Dietrich Burde Apr 19 '17 at 9:28
• the solution is not so simple, see WolframAlpha – Dr. Sonnhard Graubner Apr 19 '17 at 9:35
• Sorry, add the condition $n \geq 3$ – joy Apr 19 '17 at 9:39
• @ Dr. Sonnhard Graubner, kindly provide me the link. – joy Apr 19 '17 at 9:40