0

I have problems with solving recurrences using changing variables, The recurrence relation is: $a_n = -2n a_{n-1} + 3n(n - 1) a_{n-2}$

$a_0 = 1$

$a_1 = 2$

The solution in my book is as follows Letting $b_n = \frac{a_n}{n!}$ => $a_n = n! b_n$ And , $a_{n-1} = (n - 1)! b_{n-1}$ , $a_{n-2} = (n - 2)! b_{n-2}$ And it goes on .. I dont have any idea of what it is doing , very unclear, Im not that unfamilar with solving by changing variables but, I cant figure this out. Any help would be great .. Thank you ..

bhd
  • 71

2 Answers2

5

Hint: Let $b_n=\frac{a_n}{n!}$ for all $n$, so that $a_n=n!b_n$. Then making the appropriate substitutions, $n!b_n=-2n(n-1)!b_{n-1}+3n(n-1)(n-2)!b_{n-2}$. Then you can divide by $n!$ and have the simpler recurrence $b_n=-2b_{n-1}+3b_{n-2}$.

Ian Cavey
  • 703
  • Thanks for the reply, how did you get $b_n=n!a_n$? – bhd Nov 28 '15 at 21:57
  • I dont know why it first let $b_n= \frac{a_n}{n!}$ – bhd Nov 28 '15 at 22:00
  • I first tried using the $b_n$ that your book suggests, and just noticed that it worked better the other way around to be honest. – Ian Cavey Nov 28 '15 at 22:12
  • I should add that my book didnt give any hint. It was the answer actually , I still cant figure this one out – bhd Nov 28 '15 at 22:15
  • All of a sudden it expresses to first let $b_n= \frac{a_n}{n!}$, but why on earth ! – bhd Nov 28 '15 at 22:16
  • Oh whoops, I wrote the original substitution backwards, your book is correct. I'll edit. – Ian Cavey Nov 28 '15 at 22:20
  • thanksx but may you please explain why to divide $a_n$ by n! .. ? How you find out to perform such way – bhd Nov 28 '15 at 22:28
  • You just have to notice that it will work out I guess. You can often make up a new sequence related to the original one if it simplifies the problem. I've seen this trick before, and now so have you. It's just something to keep in the toolbox of tricks for this type of problem. – Ian Cavey Nov 28 '15 at 22:31
  • thank you very much for your time, I hate recurrences :(( – bhd Nov 28 '15 at 22:33
2

Following the hint, we now have the difference equation \begin{align*} n!b_n &= -2n(n-1)!b_{n-1} + 3n(n-1)(n-2)!b_{n-2} \\ &=-2n!b_{n-1} + 3n!b_{n-2} \end{align*} Dividing both sides by $n!$ yields the linear second order difference equation $$b_n = -2b_{n-1} + 3b_{n-2}$$ Solving this yields $$b_n = c_1(-3)^n + c_2$$ From this, and undoing the substitution we have $$a_n = c_1n!(-3)^n + c_2n!$$ The initial conditions yields $$a_n = -\dfrac{1}{4}n!(-3)^n + \dfrac{5}{4}n!$$

Nigel Overmars
  • 3,678
  • Thanks for the reply , im trying to figure out the very first steps of the solution. – bhd Nov 28 '15 at 22:03