Waste less time on Facebook — follow Brilliant.
×

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\).

Thanks! :) Please help reshare this too!

Note by Happy Melodies
3 years, 5 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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....

Eddie The Head - 3 years, 5 months ago

Log in to reply

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?

Patrick Corn - 3 years, 5 months ago

Log in to reply

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.

Daniel Liu - 3 years, 5 months ago

Log in to reply

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 \).

Patrick Corn - 3 years, 5 months ago

Log in to reply

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.

Daniel Liu - 3 years, 5 months ago

Log in to reply

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.

Daniel Liu - 3 years, 5 months ago

Log in to reply

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

Happy Melodies - 3 years, 5 months ago

Log in to reply

a1=1,a2=3,a3=9,a4=31

Sai Satti - 3 years, 4 months ago

Log in to reply

I would use generating functions.

Sean Roberson - 3 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...