Recurrence relation problem, need help:) 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}$?
 A: 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}$.

A: 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
A: Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, and write your recurrence as:
$\begin{equation*}
a_{n + 1}
  = \sum_{0 \le k \le n} (k + 1) a_{n - k}
\end{equation*}$
Multiply the recurrence by $z^n$ and sum over $n \ge 0$, recognize some sums and use $a_0 = 1$:
$\begin{align*}
\sum_{n \ge 0} a_{n + 1} z^n
   &= \sum_{n \ge 0} z^n \sum_{0 \le k \le n} (k + 1) a_{n - k} \\
\frac{A(z) - a_0}{z}
   &= \left( \sum_{n \ge 0} (n + 1) z^n \right)
        \cdot \left( \sum_{n \ge 0} a_n z^n \right) \\
\frac{A(z) - 1}{z}
   &= \left( \frac{d}{d z} \sum_{n \ge 0} z^n \right) \cdot A(z) \\
   &= \left( \frac{d}{d z} \frac{1}{1 - z} \right) \cdot A(z) \\
   &= \frac{A(z)}{(1 - z)^2}
\end{align*}$
Solving for $A(z)$, as partial fractions:
$\begin{align*}
A(z)
  &= \frac{(1 + z)^2}{1 - 3 z + z^2} \\
  &= \frac{\sqrt{5}}{5} \cdot \frac{1}{1 - z \frac{3 + \sqrt{5}}{2}}
       - \frac{\sqrt{5}}{5} \cdot \frac{1}{1 - z \frac{3 - \sqrt{5}}{2}}
       + 1
\end{align*}$
We are after the coefficient of $z^n$, the expression is just geometric series:
$\begin{equation*}
[z^n] A(z)
   = \frac{\sqrt{5}}{5}
       \cdot \left(
               \left( \frac{3 + \sqrt{5}}{2} \right)^n
                 - \left( \frac{3 - \sqrt{5}}{2} \right)^n
             \right)
       + [n = 0]
\end{equation*}$
Here $[\mathit{condition}]$ is Iverson's convention: $1$ if the condition is true, $0$ if it is false.
