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}$?
Asked
Active
Viewed 120 times
1
-
2Have you tried doing that? – Avi Steiner Sep 17 '13 at 16:14
3 Answers
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}$.
Calvin Lin
- 68,864
0
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.
vonbrand
- 27,812
