×

# Need help for Recurrence!

Hello! Any hints for this? (Characteristic eqn doesn't seem to work for me here...)

$$a_n = (n-1) a_{n-1} +n$$.

Note by Happy Melodies
2 years, 10 months ago

Sort by:

You have to do plug and chug

This is called plug :

$a_n = (n-1)((n-2)a_{n-2}+n-1) + n$

This is called chug

$a_n = (n-1)(n-2)a_{n-2}+(n-1)^{2}+n$

Continue doing this until you arrive at a base case....You can see the general form after a few chugs. which you can prove by induction.... · 2 years, 10 months ago

Divide through by $$(n-1)!$$ to get $$\frac{a_n}{(n-1)!} = \frac{a_{n-2}}{(n-2)!} + \frac{n}{(n-1)!}$$. Then if we let $$b_n = \frac{a_n}{(n-1)!}$$, we should have $$b_1 = a_1$$ and $$b_n = b_{n-1} + \frac{n}{(n-1)!}$$, so $$b_n = a_1 + \sum_{k=2}^{n} \frac{k}{(k-1)!}$$. Then $$a_n = a_1(n-1)! + \sum_{k=2}^n \frac{k(n-1)!}{(k-1)!}$$. Perhaps that sum has a nice simple closed form? · 2 years, 10 months ago

Is there a nice way to express the summation in a closed form? Summations in general do not count as a closed form. $$\displaystyle\sum_{i=1}^ni$$ is not a closed form, but $$\dfrac{n(n+1)}{2}$$ is. · 2 years, 10 months ago

No, I don't think so. Although $$\sum \frac{(k-2)}{(k-1)!}$$ is telescoping, this still leaves $$\sum \frac2{(k-1)!}$$, twice the partial sum for $$e$$. · 2 years, 10 months ago

I don't think there is an easy way to do this. Clearly there is no characteristic polynomial as the coefficients are variable. I plugged it into wolfram alpha after working on it to no avail and its general form is $a_n=2e\Gamma(n,1)-1$ where $$a_1=1$$.

$$\Gamma(a,x)$$ is the Incomplete Gamma Function which I have no clue of its definition. · 2 years, 10 months ago

My original strategy was to substitute $$b_n=a_{n+1}-c_1a_n$$ for some constant $$c$$ such that everything cancels out neatly, but it got really messy and I ended up having $$c_1=\dfrac{-n+\sqrt{n^2-4}}{2}$$ (which is almost certainly wrong) then I stopped. · 2 years, 10 months ago

Yes me too! I got that too, but it doesn't work the same way as typical characteristic eqn with variables... · 2 years, 10 months ago

a1=1,a2=3,a3=9,a4=31 · 2 years, 9 months ago