Generating functions, binomial coefficients

[Sarina3003]

Homework Statement

a) I have to find and expression for sequence of $b_n$ in terms of generating functions of the sequence of $a_n$

$$b_n = (-1)^{n}(n+1)a_0 +(-1)^{n-1}n a_1+...+(-1)2a_{n-1}+a_n$$ with $$a_n = a_{n-1} +8a_{n-2} -12a_{n-3} +25(-3)^{n-2} + 32n^2 -64$$

b) I have to use the result of a) to prove this identity

$${\beta \choose n} = \sum_{x = 0}^{n}(-1)^{x}(x+1) {\beta+2 \choose {n-x}}$$ with $\beta$ is a complex number

Homework Equations

[/B]
All necessary information are given above

3. The Attempt at a Solution
What I've already had is the GF of $a_n$ which is

$$\frac{120}{1-2z} + \frac{150}{(1-2z)^{2}} -\frac{125}{1+3z} + \frac{-3}{(1+3z)^{2}} + \frac{-83z^{2} + 202z -135}{(z-1)^{3}}$$

Please shed some lights. Any hints would be greatly appreciated

 

[Ray Vickson]

Homework Statement

a) I have to find and expression for sequence of $b_n$ in terms of generating functions of the sequence of $a_n$

$$b_n = (-1)^{n}(n+1)a_0 +(-1)^{n-1}n a_1+...+(-1)2a_{n-1}+a_n$$ with $$a_n = a_{n-1} +8a_{n-2} -12a_{n-3} +25(-3)^{n-2} + 32n^2 -64$$

b) I have to use the result of a) to prove this identity

$${\beta \choose n} = \sum_{x = 0}^{n}(-1)^{x}(x+1) {\beta+2 \choose {n-x}}$$ with $\beta$ is a complex number

Homework Equations

[/B]
All necessary information are given above

3. The Attempt at a Solution
What I've already had is the GF of $a_n$ which is

$$\frac{120}{1-2z} + \frac{150}{(1-2z)^{2}} -\frac{125}{1+3z} + \frac{-3}{(1+3z)^{2}} + \frac{-83z^{2} + 202z -135}{(z-1)^{3}}$$

Please shed some lights. Any hints would be greatly appreciated

Please refrain from typing your material in a bold font.

Anyway, you need to specify some boundary conditions on the $a_n$, such as values of $a_0, a_1$ and $a_2$. If you give different boundary conditions you will get different sequences $\{ a_n \}$ and so different generating functions.

You need to figure out how to express the generating function $B(z) = \sum_{n=0}^{\infty} b_ n z^n$ of $\{b_n \}$ in terms of the generating function $A(z) = \sum_{n=0}^{\infty} a_n z^n$ of $\{ a_n \}$.

 

[Sarina3003]

Please refrain from typing your material in a bold font.

Anyway, you need to specify some boundary conditions on the $a_n$, such as values of $a_0, a_1$ and $a_2$. If you give different boundary conditions you will get different sequences $\{ a_n \}$ and so different generating functions.

You need to figure out how to express the generating function $B(z) = \sum_{n=0}^{\infty} b_ n z^n$ of $\{b_n \}$ in terms of the generating function $A(z) = \sum_{n=0}^{\infty} a_n z^n$ of $\{ a_n \}$.

Thanks for that. Should i take the sums of both sides and see what happens? I’m not sure if it is ok since this is a sequence

 

[Ray Vickson]

Thanks for that. Yeah i know that, it is the question . But i don’t know how to start off since the recurrence relation they have for $b_n$ includes both terms $a_n$ and $b_n$

Were you given the generating function $A(z)$ as part of the problem statement? If so, you can expand it in powers of $z$ (or, at least find the first few terms) to actually obtain explicitly the values of $a_0, a_1, a_2$. If you were not given the generating function $A(a)$ you must have known the values of $a_0, a_1, a_2$ when you computed it.

Anyway, the first few terms of your $b_n$-recurrence read as
$$\begin{array}{rcl}
b_0 &=& a_0 \\
b_1&=& -2 a_0 + a_1 \\
b_2 &=& 3 a_0 - 2 a_1 + a_2 \\
b_3 &=& -4 a_0 + 3 a_1 - 2 a_2 + a_3 \\
\vdots & \vdots & \hspace{2ex}\vdots
\end{array}
$$
Thus, we have
$$B(z) = a_0 - 2 a_0 z + 3 a_0 z^2 + \cdots -2 a_1 z^2 + 3 a_1 z^3 + \cdots \\
+ a_2 z^2 - 2 a_2 z^3 + \cdots + a_3 z^3 - \cdots $$
Isolate the total coefficients of each $a_i$, then sum up the results.

 

[Sarina3003]

Were you given the generating function $A(z)$ as part of the problem statement? If so, you can expand it in powers of $z$ (or, at least find the first few terms) to actually obtain explicitly the values of $a_0, a_1, a_2$. If you were not given the generating function $A(a)$ you must have known the values of $a_0, a_1, a_2$ when you computed it.

Anyway, the first few terms of your $b_n$-recurrence read as
$$\begin{array}{rcl}
b_0 &=& a_0 \\
b_1&=& -2 a_0 + a_1 \\
b_2 &=& 3 a_0 - 2 a_1 + a_2 \\
b_3 &=& -4 a_0 + 3 a_1 - 2 a_2 + a_3 \\
\vdots & \vdots & \hspace{2ex}\vdots
\end{array}
$$
Thus, we have
$$B(z) = a_0 - 2 a_0 z + 3 a_0 z^2 + \cdots -2 a_1 z^2 + 3 a_1 z^3 + \cdots \\
+ a_2 z^2 - 2 a_2 z^3 + \cdots + a_3 z^3 - \cdots $$
Isolate the total coefficients of each $a_i$, then sum up the results.

Thanks so much. Yes i know a1, a2 and a0 but i used it to get GF of an. But how is it helpful in this question?

 

[Ray Vickson]

Thanks so much. Yes i know a1, a2 and a0 but i used it to get GF of an. But how is it helpful in this question?

It might not be; it is just that your presentation of the question was incomplete, and I wanted to know if you realized that. If I want to check your GF myself, I would need that information.

 

[Sarina3003]

It might not be; it is just that your presentation of the question was incomplete, and I wanted to know if you realized that. If I want to check your GF myself, I would need that information.

a0 =130, a1=215, a2=260, here they are. If you have some time, please also help me to check it whether i got it right or wrong, just by the way. Thank you :D

 

[Sarina3003]

It might not be; it is just that your presentation of the question was incomplete, and I wanted to know if you realized that. If I want to check your GF myself, I would need that information.

Also, do you have any idea for b). I got the answer for a) now, thanks to you, it looks little bit different from the identity in b) and so i guess i have to do a little bit of work to somehow use the answer from a) and arrive to the identity but since this is power series it is more little complicated to handle so i am still stuck at it :( Particularly, dealing with this bit $${\beta+2 \choose {n-x}}$$

 

[Ray Vickson]

a0 =130, a1=215, a2=260, here they are. If you have some time, please also help me to check it whether i got it right or wrong, just by the way. Thank you :D

You made an error somewhere. If we expand your given GF in powers of $z$ and look at the coefficients of $z^0, z^1, z^2$ we get $a_0 = 277, a_1 = 1436$ and $a_2 = 1361.$

If I take your $a_0 = 130, a_1 = 215, a_2 = 260$ and substitute those into the recursion, then solve it-- or, rather, let the computer algebra system Maple solve it by finding the generating function-- I get a completely different GF from yours.

I don't think the PF rules will let me present the exact form of the GF.

However, even using the (incorrect) initial conditions $a_0 = 277, a_1 = 1436$ and $a_2 = 1361$ in your recursion, Maple still gets a completely different GF from yours, so that means that your GF would not lead to a correct solution of the recursion. Somewhere, the values of $a_3, a_4, \ldots$ obtained using the (incorrect) initial conditions in the recursion would be different from the values obtained by expanding out your GF in powers of $z$.

 

[Sarina3003]

You made an error somewhere. If we expand your given GF in powers of $z$ and look at the coefficients of $z^0, z^1, z^2$ we get $a_0 = 277, a_1 = 1436$ and $a_2 = 1361.$

If I take your $a_0 = 130, a_1 = 215, a_2 = 260$ and substitute those into the recursion, then solve it-- or, rather, let the computer algebra system Maple solve it by finding the generating function-- I get a completely different GF from yours.

I don't think the PF rules will let me present the exact form of the GF.

However, even using the (incorrect) initial conditions $a_0 = 277, a_1 = 1436$ and $a_2 = 1361$ in your recursion, Maple still gets a completely different GF from yours, so that means that your GF would not lead to a correct solution of the recursion. Somewhere, the values of $a_3, a_4, \ldots$ obtained using the (incorrect) initial conditions in the recursion would be different from the values obtained by expanding out your GF in powers of $z$.

Thanks for pointing out. I have used Mathematica and typed straight in a[n] and solve it with boundary conditions and it gave me the answer include exponential which i have not seen along the way finding its solution including particular solutions . Have you seen something like that in Maple?
And yeah i did have mistakes, i have checked it, and even when i corrected it it also does not give me any exponential term :(

 

[Ray Vickson]

Thanks for pointing out. I have used Mathematica and typed straight in a[n] and solve it with boundary conditions and it gave me the answer include exponential which i have not seen along the way finding its solution including particular solutions . Have you seen something like that in Maple?
And yeah i did have mistakes, i have checked it, and even when i corrected it it also does not give me any exponential term :(

I am attempting to attach a pdf image of my Maple worksheet; I don't know if it will work as intended.

 

[Ray Vickson]

Thanks for pointing out. I have used Mathematica and typed straight in a[n] and solve it with boundary conditions and it gave me the answer include exponential which i have not seen along the way finding its solution including particular solutions . Have you seen something like that in Maple?
And yeah i did have mistakes, i have checked it, and even when i corrected it it also does not give me any exponential term :(

Oops: I see I had a wrong recursion; I wrote -64 instead of -64n on the right. I will do it again.

Attached is the new worksheet.

I forgot to simplify the result, but when I ask Maple to do that it gives
$$a_k =(-1)^k 3^k k+5(-1)^{k+1} 3^k+8k^2+60k+135.$$

This looks different from the Mathematica result, but I have checked it out in detail: it really does solve the recursion. (I got Maple to check this after making the pdf file, so that check is not included in the attachment.)

 

[Sarina3003]

Oops: I see I had a wrong recursion; I wrote -64 instead of -64n on the right. I will do it again.

Attached is the new worksheet.

I forgot to simplify the result, but when I ask Maple to do that it gives
$$a_k =(-1)^k 3^k k+5(-1)^{k+1} 3^k+8k^2+60k+135.$$

This looks different from the Mathematica result, but I have checked it out in detail: it really does solve the recursion. (I got Maple to check this after making the pdf file, so that check is not included in the attachment.)

Thank you. I have checked my calculation by hand and plug in a0,a1 and a2 and verify that it works now! Thanks for your sheets I have learned some codes in Maple as well and it would be useful when I encounter it in the near future. Thanks again :):)

 

[Ray Vickson]

Also, do you have any idea for b). I got the answer for a) now, thanks to you, it looks little bit different from the identity in b) and so i guess i have to do a little bit of work to somehow use the answer from a) and arrive to the identity but since this is power series it is more little complicated to handle so i am still stuck at it :( Particularly, dealing with this bit $${\beta+2 \choose {n-x}}$$

Presumably, you need to figure out how to get $B(z) = \sum_{n=0}^{\infty} b_n z^n$ before you can proceed further. I hinted at one way to do it in post #4, but another way is to note that the $b_n$ sequence is the convolution of the $a_n$ sequence and the sequence $\{ c_n , n = 0,1,2, \ldots \} = \{ 1, -2, 3, -4, \ldots \}$. It is quite easy to get the GF $C(z) = \sum c_n z^n$ and you can then apply some standard properties of GF to get the answer.