2
$\begingroup$

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 )$$

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for the reply. The first time I tried to solve this problem, I tried that. At that time, i think If i some over k, then I get $ G_n(x)=x(G_n(x)-f(n,n)x^n)−2xG_{n−1}(x).$ Isn't it? Can I ignore $ f(n,n){ x }^{ n+1 } $? $\endgroup$ – J.J.J.Doe May 11 '17 at 11:45
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for the reply. Can you solve the question in the above comment? $\endgroup$ – J.J.J.Doe May 11 '17 at 4:59
  • $\begingroup$ @J.J.J.Doe The only terms that are subtracted when summing over $k$ are $f(n,0)$ not $f(n,n)$. This is because the left hand side of the recurrence is one step ahead of the right hand side and so the term $f(n,0)$ on the left isn't related to previous terms by the recurrence. Fortunately $f(n,0)=0$ so it doesn't matter. If you could explain where you get $f(n,n)$ I may be able to help further. $\endgroup$ – N. Shales May 11 '17 at 9:12
  • $\begingroup$ I try this way... $ { G }_{ n }(x)=\sum _{ k=0 }^{ n }{ f(n,k) } { x }^{ k }=\sum _{ k=1 }^{ n }{ f(n,k) } { x }^{ k }=\sum _{ k=1 }^{ n }{ f(n,k-1){ x }^{ k } } -2\sum _{ k=1 }^{ n }{ f(n-1,k-1){ x }^{ k } } =x\sum _{ k=0 }^{ n-1 }{ f(n,k){ x }^{ k } } -2x\sum _{ k=0 }^{ n-1 }{ f(n-1,k){ x }^{ k } } =x(\sum _{ k=0 }^{ n }{ f(n,k){ x }^{ k } } -f(n,n){ x }^{ n })-2x{ G }_{ n-1 }(x)=x{ G }_{ n }(x)-f(n,n){ x }^{ n+1 }-2x{ G }_{ n-1 }(x) $ $\endgroup$ – J.J.J.Doe May 11 '17 at 11:33
  • $\begingroup$ @J.J.J.Doe You have assumed $G_n(x)$ is a polynomial as opposed to a series, this is the main issue. If you notice in my answer $f(n,k)=0$ for $k\lt n$, almost exactly the coefficients you have restricted yourself to. I will put up a table of values for $f(n,k)$ to clarify. $\endgroup$ – N. Shales May 11 '17 at 15:24
  • 1
    $\begingroup$ thanks very much. Now, I understand your point $\endgroup$ – J.J.J.Doe May 17 '17 at 1:58

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.