How can I find the generating function of this sequence with recurrence relation?

Question

I looked up related documents and saw a similar problem solving.
But, I don't understand well and still can not solve the problem.

How can I find the sequence of generating function ???

$${ G }_{ n }(x)=\sum _{ k=0 }^{ n }{ f(n,k){ x }^{ k } } \quad \text{with} \quad f(n,k)=f(n,k-1)-2f(n-1,k-1)$$

$$( { G }_{ 0 }=1,\quad f(n,0)=0 )$$

Answer 1

Try writing this as a series in two indeterminates $x$ and $y$ such that

$$H(x,y)=\sum_{n\ge 0}G_n(x)y^n=\sum_{k,n\ge 0}f(n,k)y^nx^k$$ $$\implies H(x,y)=\sum_{n\ge 0}f(n,0)y^n + \sum_{k\ge 1}f(0,k)x^k + \sum_{k,n\ge 1}f(n,k)y^nx^k$$

From the i.c's we get

$$H(x,y)=1+\sum_{k,n\ge 1}f(n,k)y^nx^k$$

and using $f(n,k)=f(n,k-1)-2f(n-1,k-1)$ we can write

$$\begin{align}H(x,y)&=1+\sum_{k,n\ge 1}\left(f(n,k-1)-2f(n-1,k-1)\right)y^nx^k\\ &=1+x\sum_{k,n\ge 1}f(n,k-1)y^nx^{k-1}-2xy\sum_{k,n\ge 1}f(n-1,k-1)y^{n-1}x^{k-1}\\ &=1+x\sum_{\begin{subarray}{c}k&\ge 0\\n&\ge 1\end{subarray}}f(n,k)y^nx^k-2xy\sum_{k,n\ge 0}f(n,k)y^nx^k\end{align}$$

Using our i.c $f(0,0)=1$ again gives

$$\begin{align}H(x,y)&=1+x\left(\sum_{k,n\ge 0}f(n,k)y^nx^k - 1\right) - 2xy\sum_{k,n\ge 0}f(n,k)y^nx^k\\ &=1-x+xH(x,y)-2xyH(x,y)\\ &=\frac{1-x}{1-x(1-2y)}=\left(1-\left(\frac{-2x}{1-x}\right)y\right)^{-1}\\ H(x,y)&=\sum_{n\ge 0}\left(\frac{-2x}{1-x}\right)^ny^n\\ H(x,y)&=\sum_{n\ge 0}G_n(x)y^n\end{align}$$

equating coefficients of $y^n$

$$G_n(x)=\frac{(-2)^nx^n}{(1-x)^n}$$

this can be written by expanding the negative binomial

$$\begin{align}G_n(x)&=(-2)^nx^n\sum_{k\ge 0}\binom{n+k-1}{n-1}x^k=\sum_{k\ge 0}(-2)^n\binom{n+k-1}{n-1}x^{n+k}\\ &= \sum_{k\ge n}(-2)^{n}\binom{k-1}{n-1}x^k\end{align}$$

$$\implies f(n,k)=(-2)^n\binom{k-1}{n-1}\tag{Answer}$$

check the recurrence

$$f(n,k-1)-2f(n-1,k-1)=(-2)^n\binom{k-2}{n-1}+(-2)^n\binom{k-2}{n-2}=(-2)^n\left(\binom{k-2}{n-1}+\binom{k-2}{n-2}\right)=(-2)^n\binom{k-1}{n-1}=f(n,k)$$

which (due to Pascal's identity) checks out.

---

$$\begin{array}{c} \text{Table of values for $f(n,k)$}\\ \begin{array}{c|rrrrrrrr} n \backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6&\cdots\\\hline 0&1 &0 &0 &0 &0 &0 &0&\cdots\\ 1&0 &-2 &-2 &-2 &-2 &-2 &-2&\cdots\\ 2&0 &0 &4 &8 &12 &16 &20&\cdots\\ 3&0 &0 &0 &-8 &\bbox[aqua]{-24} &-48 &-80&\cdots\\ 4&0 &0 &0 &0 &\bbox[yellow]{16} &\bbox[lime]{64} &160&\cdots\\ 5&0 &0 &0 &0 &0 &-32 &-160&\cdots\\ 6&0 &0 &0 &0 &0 &0 &64&\cdots\\ \vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\ddots\\ \end{array}\\ \end{array}$$

e.g. For $n=4$ and $k=5$ $$\begin{split}f(n,k)&=f(n,&k-1)&\:-\:&2f(n-&1,k-1)\\ \bbox[lime]{\phantom{A}}\,&=\,&\bbox[yellow]{\phantom{A}}&\:-\:&2\,&\bbox[aqua]{\phantom{A}}\end{split}$$

Answer 2

Multiply your recurrence relation by $x^k$ to get $$ f(n,k) x^k = f(n,k-1)x^k - 2f(n-1,k-1) x^k.$$

Sum over $k$ to get $$G_n(x) = x G_n(x) - 2 x G_{n-1}(x).$$

Solving for $G_n(x)$ gives $$G_n(x) = \frac{-2x}{1 - x} G_{n-1}(x).$$

Since $G_0(x) = 1$, this implies $$G_n(x) = \left(\frac{-2 x}{1 - x} \right)^n$$