I am new to generating function and having a hard time figuring out generating function using sequence. The question that I am having trouble on is using the sequence ar = $\sum_{i=0}^{n} \binom{i} {r} $, find the generating function. There is a hint using $\sum_{r>=0}{}$ ar $x^r $. I the r in ar is lower Can you please help. Thank you.
5
-
$\begingroup$ "There is a hint using" ... ? $\endgroup$Henry– Henry2020-11-01 02:29:20 +00:00Commented Nov 1, 2020 at 2:29
-
$\begingroup$ Is the sequence $a_r$? Is it $a_r = \sum_{i = 0}^r {r \choose i}$? $\endgroup$DavidW– DavidW2020-11-01 02:51:30 +00:00Commented Nov 1, 2020 at 2:51
-
$\begingroup$ @DavidW yes, my bad $\endgroup$Ta Anh Minh– Ta Anh Minh2020-11-01 04:21:23 +00:00Commented Nov 1, 2020 at 4:21
-
$\begingroup$ What is $n$ here? Did you want to type $ \sum\limits_{i=0}^{r}$ instead? $\endgroup$Kavi Rama Murthy– Kavi Rama Murthy2020-11-01 04:52:50 +00:00Commented Nov 1, 2020 at 4:52
-
$\begingroup$ The question says its n so i cannot change it. $\endgroup$Ta Anh Minh– Ta Anh Minh2020-11-01 04:59:53 +00:00Commented Nov 1, 2020 at 4:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
The generating function for the sequence $\langle a_r:r\ge 0\rangle$ is by definition
$$g(x)=\sum_{r\ge 0}a_rx^r\,;$$
since $a_r=\sum_{i=0}^n\binom{i}r$, we can write this as
$$g(x)=\sum_{r\ge 0}\sum_{i=0}^n\binom{i}rx^r\,.$$
$\binom{i}r=0$ when $i<r$, so every term of $a_r=\sum_{i=0}^n\binom{i}r$ is $0$ when $r>n$. This means that $a_r=0$ when $r>n$, so
$$g(x)=\sum_{r=0}^n\sum_{i=0}^n\binom{i}rx^r\,:$$
it’s actually a polynomial of degree $n$.
$$\begin{align*} g(x)&=\sum_{r=0}^n\sum_{i=0}^n\binom{i}rx^r\\ &=\sum_{i=0}^n\sum_{r=0}^n\binom{i}rx^r\\ &=\sum_{i=0}^n\sum_{r=0}^i\binom{i}rx^r\cdot 1^{i-r}\\ &=\sum_{i=0}^n(x+1)^i\,. \end{align*}$$
This is a finite geometric series, so you should be able to express it in closed form; it’s not hard to simplify that closed form to a polynomial.
That approach works even if you know only the most basic facts about binomial coefficients. If you know the hockey stick identity, you can rewrite $g(x)$ as
$$\sum_{i=0}^nx^r\sum_{r=0}^n\binom{i}r$$
and apply the hockey stick identity to get the polynomial directly.
-
$\begingroup$ I will continue the step and can you correct me if i am wrong. $\sum_{i=0}^{n} (x+1)^i = 1 + (x+1)^1 + ... + (x+1)^n = S $. Then I get $(x+1)S = (x+1)^1 + (x+1)^2 + ... + (x+1)^n * (x+1)$. Subtract S from (x+1)S --> $S - (x+1)S = 1 - (x+1)^n * (x+1)$ --> $xS = 1 - (x+1)^n * (x+1) $. Therefore, the close form of g(x) is $S = \frac{1 - (x+1)^n * (x+1)}{x}$. $\endgroup$Ta Anh Minh– Ta Anh Minh2020-11-01 17:03:01 +00:00Commented Nov 1, 2020 at 17:03
-
$\begingroup$ @TaAnhMinh: Almost, but you have a sign error: it’s $$\frac{(x+1)^{n+1}-1}x\,.$$ And after you expand $(x+1)^{n+1}$ using the binomial theorem and subtract $1$, there will be a factor of $x$ to cancel, leaving a polynomial. $\endgroup$Brian M. Scott– Brian M. Scott2020-11-01 18:54:35 +00:00Commented Nov 1, 2020 at 18:54
-
1$\begingroup$ oh yes, i forgot about the sign. So S - (x+1) S = -xS = $ 1-(x+1)^{n+1}$. Then S = $\frac{(x+1)^{n+1}-1} {x}$. Thank you very much $\endgroup$Ta Anh Minh– Ta Anh Minh2020-11-01 19:01:10 +00:00Commented Nov 1, 2020 at 19:01
-
1$\begingroup$ @TaAnhMinh: By the binomial theorem $$(x+1)^{n+1}=\sum_{k=0}^{n+1}\binom{n+1}kx^k\,;$$ the constant term is $\binom{n+1}0=1$, so subtracting $1$ leaves $\sum_{k=1}^{n+1}x^k$, and dividing by $x$ and shifting the index leaves $\sum_{k=0}^n\binom{n+1}{k+1}x^k$. $\endgroup$Brian M. Scott– Brian M. Scott2020-11-01 19:07:00 +00:00Commented Nov 1, 2020 at 19:07
-
1$\begingroup$ @TaAnhMinh: That’s correct. $\endgroup$Brian M. Scott– Brian M. Scott2020-11-01 23:10:24 +00:00Commented Nov 1, 2020 at 23:10