How do I go from the following recurrence relation

a(n) = (n+1)a(n-1) where a(0) = 2

to a closed form? I know I need to use an iterative approach but I am not quite sure what to look for.


We can divide through by the summation factor $(n+1)!$ to get $${a_n\over (n+1)!}=\frac{a_{n-1}}{n!}$$ Now let $$S_n:=\frac{a_n}{(n+1)!}$$ Thus $S_n=S_{n-1}=c$ is constant, but $a_0=2$ and so $S_0=2/1=2\implies S_n\equiv2$ Thus we have $$a_n=(n+1)!S_n=2\cdot (n+1)!$$

  • $\begingroup$ Thank you, and if I wanted to prove that this answer was correct, would I do that with a proof by induction or what? $\endgroup$ – DrJonesYu Apr 28 '14 at 1:20
  • 1
    $\begingroup$ This is sufficient proof in my opinion. You could certainly verify it that way, but there's nothing wrong with a direct derivation. $\endgroup$ – user142299 Apr 28 '14 at 1:24
  • $\begingroup$ What is the approach called that you took to solve this? $\endgroup$ – DrJonesYu Apr 28 '14 at 1:31
  • $\begingroup$ I'm not sure - I learned it originally from the book "Concrete Mathematics" by Knuth, et al. See this: homepages.gac.edu/~holte/courses/mcs256/documents/… They show how to find $S_n$ in general. This method can be used to solve any recurrence of the form $a_nx_n=b_nx_{n-1}+c_n$ so it's fairly powerful and nice to know. $\endgroup$ – user142299 Apr 28 '14 at 1:34

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.