Recurrence relation problem, need help:)

Question

I´m stuck on a problem. Can anyone help me? The problem: Find the recurrence relation to

$$a_n=a_{n-1}+2a_{n-2}+\cdots+(n-1)a_1+na_0\;(\text{for }n\ge 1),\\a_0=1$$

I guess I have to compare $a_n-a_{n-1}$ with $a_{n-1}-a_{n-2}$?

Answer 1

Hint: In your own hint, substitute $a_n$, $a_{n-1}$, $a_{n-2}$ with the formula that you are given.

What is the recurrence relation that you get?

$a_{n} = 3 a_{n-1} - a_{n-2}$.

Answer 2

And in the worst case if it's a bad day OEIS is allways there... ;)

http://oeis.org/search?q=1%2C+1%2C+3%2C+8%2C+21%2C+55%2C+144%2C+377%2C+987&language=english&go=Search