# 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}$?

• Have you tried doing that? – Avi Steiner Sep 17 '13 at 16:14

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

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

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.