1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Have you tried doing that? $\endgroup$ – Avi Steiner Sep 17 '13 at 16:14
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.