recurrence relations and generating functions - I need a hint

Question

I need to find "closed form" to the recurrence relation given by: $a_{n+1} = \sum_{k=0} ^ {n} k a_{n-k}$ and $a_0 = 1$. I have tried using generating functions but it is no good. Any help would be appreciated!

Answer 1

The first problem is to reshape the given recurrence relation. Move the left hand side to the right giving $0=\sum_{k=-1}^nka_{n-k}$ for $n\geq0$. Then rename $k$ and $n$ such that both have values $1$ more than before, giving $0=\sum_{k=0}^n(k-1)a_{n-k}$ for $n\geq1$. Finally incorporate the initial condition in the modified form $\sum_{k=0}^0(k-1)a_{n-k}=-1$. So the recurrence relation and initial condition can be captured in $$ \sum_{k=0}^n(k-1)a_{n-k}=-\delta_{n,0} \qquad\text{for all $n\geq0$.} $$ Now the equation states an easy relation between generating functions: with $F=\sum_k(k-1)X^k$ and $A=\sum_la_lX^l$ it states $FA=-1$. This means that $A$ is the inverse generating function of $-F$. Expressing $-(k-1)=2-(k+1)=(-1)^k(2\binom{-1}k-\binom{-2}k)$ and using the binomial formula for exponents $-1,-2$ gives $$-F=\frac2{1-X}-\frac1{(1-X)^2}=\frac{1-2X}{(1-X)^2},$$ whence $$A=\sum_la_lX^l=\frac{(1-X)^2}{1-2X}=1+\frac{X^2}{1-2X},$$ where the last equality results from a polynomial division by rising powers of $(1-X)^2$ by $1-2X$. It leads to an explicit expression solving the recurrence: $a_0=1$, $a_1=0$, and $a_{i+2}=2^i$ for $i\geq2$.

Answer 2

Note that for $n\geq1$ one has: $$a_{n+1}-a_n =\sum_{k=0}^nka_{n-k}-\sum_{k=0}^{n-1}ka_{n-k-1} =\sum_{k=1}^nka_{n-k}-\sum_{k=1}^{n}(k-1)a_{n-k} =\sum_{k=1}^na_{n-k}.$$ Thus, $a_{n+1}=\sum_{k=0}^na_{n-k}$ for $n\geq1$.

Can you take it from here?

Answer 3

Define the generating functiom:

$$ A(z) = \sum_{n \ge 0} a_n z^n $$

Multiply the recurrence by $z^n$, sum over $n \ge 0$:

$\begin{align} \sum_{n \ge 0} a_{n + 1} z^n &= \sum_{n \ge 0} \sum_{0 \le k \le n} k a_{n - k} z^n \\ \frac{A(z) - a_0}{z} &= \left( \sum_{n \ge 0} n z^n \right) \left( \sum_{n \ge 0} a_n z^n \right) \\ \frac{A(z) - 1}{z} &= \frac{z}{(1 - z)^2} A(z) \end{align}$

Solve for $A(z)$, as partial fractions:

$\begin{align} A(z) &= \frac{3}{4} - \frac{1}{2} z + \frac{1}{4} \frac{1}{1 - 2 z} \end{align}$

Thus:

$\begin{align} a_n = \begin{cases} 1 & n = 0 \\ 0 & n = 1 \\ 2^{n - 2} & n \ge 2 \end{cases} \end{align}$