Reccurence Relation for columns of Pascal's triangle

Question

I am given the recurrence equation $$F_k(n) = \sum_{j = 0}^{k - 1}(-1)^j\binom{k}{j + 1}F_k(n - j - 1)$$ and asked to solve it. Here k is a positive integer and $F_k(k - 1) = 1$ and $F_k(n) = 0$, $n < k -1$ I have a conjecture that the solution is $$F_k(n) = \frac{(n-(k - 2))^{\underline{k - 1}}}{(k - 1)!}$$ and have tried to prove it by induction but I get stuck. I know this works because these values are the diagonals on pascal's triangle but I am not sure how to finish the induction proof for the solving of the recurrence.

Answer 1

The result can be derived using generating functions. The recurrence can be written as $$F_k(n)=\sum_{j=1}^{k}(-1)^{j-1}\binom{k}{j}F_k(n-j)$$ (for a bit nicer look) and is valid for $n\geqslant k$. Now suppose $k$ is fixed, and let $F(x)=\sum\limits_{n=0}^{\infty}F_k(n)x^n$. Then, multiplying the recurrence by $x^n$ and summing over $n\geqslant k$, you find \begin{align} F(x)-x^{k-1}&=\sum_{n=k}^{\infty}x^n\sum_{j=1}^{k}(-1)^{j-1}\binom{k}{j}F_k(n-j)\\&=\sum_{j=1}^{k}(-1)^{j-1}\binom{k}{j}x^j\sum_{n=k}^{\infty}F_k(n-j)x^{n-j}\\&=F(x)\sum_{j=1}^{k}(-1)^{j-1}\binom{k}{j}x^j\\&=F(x)\big(1-(1-x)^k\big), \end{align} i.e. $F(x)=x^{k-1}/(1-x)^k$. The power series for this is well-known, or can be obtained from $$\frac{1}{(1-x)^k}=\frac{1}{(k-1)!}\frac{d^{k-1}}{dx^{k-1}}\left[\frac{1}{1-x}=\sum_{n=0}^{\infty}x^n\right].$$