I need this as part of a bigger proof.

Does \begin{align} G_1 &\longleftrightarrow \Big\{\binom{n}{k}\Big\}_{2k=0}^r \notag \\ \implies G_1(z) &= (1 + z^2)^r \end{align}

Help me prove this as it would help me with the bigger problem I'm doing.

I know the ordinary generating function of $\Big\{\binom{r}{k}\Big\}_{k=0}^r$ is $(1 + z)^r$.

Here is the original problem and my working.

Find a generating function $G(z)$ for which $$[z^n]G(z) = \sum_{k_0 + 2k_1 + 4k_2 + 8k_3 + \dots =n} \binom{r}{k_0}\binom{r}{k_1}\binom{r}{k_2}\binom{r}{k_3}\dots$$

The fact that all the sum of all the indices of summation is always constant suggests that $G(z)$ is the product of several different generating functions. \begin{align} \text{The generating function of }G_1 &\longleftrightarrow \Big\{\binom{r}{k_0}\Big\}_{k_0 = 0}^r \notag \\ \implies G_1(z) &= (1+z)^r \\ \text{The generating function of }G_2 &\longleftrightarrow \Big\{\binom{r}{k_1}\Big\}_{2k_1 = 0}^r \notag \\ \implies G_2(z) &= (1+z^2)^r \\ \text{The generating function of }G_3 &\longleftrightarrow \Big\{\binom{r}{k_2}\Big\}_{4k_2 = 0}^r \notag \\ \implies G_3(z) &= (1+z^4)^r\\ \vdots \notag \\ \text{The generating function $G(z)$ can be gotten by multiplying all these functions}G(z) &= G_1(z)G_2(z)G_3(z)\dots \notag \\ &=(1+z)^r(1+z^2)^r(1+z^4)^r\dots \notag \\ \implies G(z) &=\Big(\frac{1}{1-z}\Big)^r \\ \text{Now, we have gotten the generating function. The sum is }&\binom{r+n-1}{n} \end{align}

  • 2
    $\begingroup$ What is $\Big\{\binom{n}{k}\Big\}_{2k=0}^r$? $\endgroup$ – Ross Millikan Jul 3 '16 at 14:00
  • $\begingroup$ @RossMillikan It's a sequence of numbers. $G_1(z)$ is the generating function of that sequence. $\endgroup$ – user230452 Jul 3 '16 at 14:02
  • $\begingroup$ @RossMillikan Please help me, Ross. You can do it. $\endgroup$ – user230452 Jul 3 '16 at 14:07
  • $\begingroup$ In your last, it is only $(1+z)^r$ if $r=n$. Is that true in the case you want? $\endgroup$ – Ross Millikan Jul 3 '16 at 14:17
  • $\begingroup$ @RossMillikan That was a typo $\endgroup$ – user230452 Jul 3 '16 at 14:18

By the Binomial theorem,

$$(1+z^2)^r=\sum_{k=0}^r\binom rkz^{2k}$$ hence $G_{1,2k}=\binom rk$ and $G_{1,2k+1}=0$.

  • $\begingroup$ I don't understand what the subscripts are ? What do they represent ? $\endgroup$ – user230452 Jul 3 '16 at 14:52
  • 1
    $\begingroup$ @user230452: are you serious ? $\endgroup$ – Yves Daoust Jul 3 '16 at 14:54
  • $\begingroup$ Yes, you are using two subscripts. That's what's confusing me. $\endgroup$ – user230452 Jul 3 '16 at 14:59
  • $\begingroup$ @user230452 The first is yours ! $\endgroup$ – Yves Daoust Jul 3 '16 at 15:24
  • $\begingroup$ Ok, thanks. ${}$ $\endgroup$ – user230452 Jul 3 '16 at 15:26

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.