Prove the generating function $\sum _{N\ge 0}{\textstyle (}\genfrac{}{}{0ex}{}{M+N}{N}{\textstyle )}{x}^{N}=\frac{1}{(1-x{)}^{M+1}}$

Joshua Foley
2022-07-07
Answered

Prove the generating function $\sum _{N\ge 0}{\textstyle (}\genfrac{}{}{0ex}{}{M+N}{N}{\textstyle )}{x}^{N}=\frac{1}{(1-x{)}^{M+1}}$

You can still ask an expert for help

Nirdaciw3

Answered 2022-07-08
Author has **20** answers

Step 1

You can prove it by induction.

$P(k):\frac{1}{(1-x{)}^{m+1}}=\sum _{i=0}^{\mathrm{\infty}}{\textstyle (}\genfrac{}{}{0ex}{}{m+i}{i}{\textstyle )}{x}^{i}$

P(0) is true, so we have $\frac{1}{1-x}=\sum _{i=0}^{\mathrm{\infty}}{x}^{i}$.

Assume P(n) is true, and multiply both sides by $\frac{1}{1-x}$.

$\frac{1}{(1-x{)}^{m+2}}=\left(\sum _{j=0}^{\mathrm{\infty}}{x}^{j}\right)\left(\sum _{i=0}^{\mathrm{\infty}}{\textstyle (}\genfrac{}{}{0ex}{}{m+i}{i}{\textstyle )}{x}^{i}\right)$

i and j are independent, so the sums can be nested.

$=\sum _{i=0}^{\mathrm{\infty}}{\textstyle (}\genfrac{}{}{0ex}{}{m+i}{i}{\textstyle )}\sum _{j=0}^{\mathrm{\infty}}{x}^{i+j}$

Step 2

Let $i+j=k$. Note that this is a different j from the previous equation, and because $i\ge 0$, the new j is capped at k.

$=\sum _{k=0}^{\mathrm{\infty}}\sum _{j=0}^{k}{\textstyle (}\genfrac{}{}{0ex}{}{m+k-j}{k-j}{\textstyle )}{x}^{k}$

By the hockey-stick identity and the independence of j, the inner sum can be re-written.

$=\sum _{k=0}^{\mathrm{\infty}}{\textstyle (}\genfrac{}{}{0ex}{}{m+1+k}{k}{\textstyle )}{x}^{k}$

You can prove it by induction.

$P(k):\frac{1}{(1-x{)}^{m+1}}=\sum _{i=0}^{\mathrm{\infty}}{\textstyle (}\genfrac{}{}{0ex}{}{m+i}{i}{\textstyle )}{x}^{i}$

P(0) is true, so we have $\frac{1}{1-x}=\sum _{i=0}^{\mathrm{\infty}}{x}^{i}$.

Assume P(n) is true, and multiply both sides by $\frac{1}{1-x}$.

$\frac{1}{(1-x{)}^{m+2}}=\left(\sum _{j=0}^{\mathrm{\infty}}{x}^{j}\right)\left(\sum _{i=0}^{\mathrm{\infty}}{\textstyle (}\genfrac{}{}{0ex}{}{m+i}{i}{\textstyle )}{x}^{i}\right)$

i and j are independent, so the sums can be nested.

$=\sum _{i=0}^{\mathrm{\infty}}{\textstyle (}\genfrac{}{}{0ex}{}{m+i}{i}{\textstyle )}\sum _{j=0}^{\mathrm{\infty}}{x}^{i+j}$

Step 2

Let $i+j=k$. Note that this is a different j from the previous equation, and because $i\ge 0$, the new j is capped at k.

$=\sum _{k=0}^{\mathrm{\infty}}\sum _{j=0}^{k}{\textstyle (}\genfrac{}{}{0ex}{}{m+k-j}{k-j}{\textstyle )}{x}^{k}$

By the hockey-stick identity and the independence of j, the inner sum can be re-written.

$=\sum _{k=0}^{\mathrm{\infty}}{\textstyle (}\genfrac{}{}{0ex}{}{m+1+k}{k}{\textstyle )}{x}^{k}$

Esmeralda Lane

Answered 2022-07-09
Author has **7** answers

Step 1

You can also obtain the generating function directly via stars-and-bars. Fix M, and let aN be the number of nonnegative integer solutions of

${y}_{1}+\cdots +{y}_{M+1}=N.$

Then ${a}_{N}={\textstyle (}\genfrac{}{}{0ex}{}{(M+1)+N-1}{(M+1)-1}{\textstyle )}={\textstyle (}\genfrac{}{}{0ex}{}{M+N}{M}{\textstyle )}={\textstyle (}\genfrac{}{}{0ex}{}{M+N}{N}{\textstyle )}.$

Step 2

So $\sum _{N=0}^{\mathrm{\infty}}{\textstyle (}\genfrac{}{}{0ex}{}{M+N}{N}{\textstyle )}{x}^{N}=\sum _{N=0}^{\mathrm{\infty}}{a}_{N}{x}^{N}={\left(\sum _{k=0}^{\mathrm{\infty}}{x}^{k}\right)}^{M+1}={\left(\frac{1}{1-x}\right)}^{M+1}=\frac{1}{(1-x{)}^{M+1}}$

You can also obtain the generating function directly via stars-and-bars. Fix M, and let aN be the number of nonnegative integer solutions of

${y}_{1}+\cdots +{y}_{M+1}=N.$

Then ${a}_{N}={\textstyle (}\genfrac{}{}{0ex}{}{(M+1)+N-1}{(M+1)-1}{\textstyle )}={\textstyle (}\genfrac{}{}{0ex}{}{M+N}{M}{\textstyle )}={\textstyle (}\genfrac{}{}{0ex}{}{M+N}{N}{\textstyle )}.$

Step 2

So $\sum _{N=0}^{\mathrm{\infty}}{\textstyle (}\genfrac{}{}{0ex}{}{M+N}{N}{\textstyle )}{x}^{N}=\sum _{N=0}^{\mathrm{\infty}}{a}_{N}{x}^{N}={\left(\sum _{k=0}^{\mathrm{\infty}}{x}^{k}\right)}^{M+1}={\left(\frac{1}{1-x}\right)}^{M+1}=\frac{1}{(1-x{)}^{M+1}}$

asked 2020-11-09

Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.

asked 2021-07-28

Let A, B, and C be sets. Show that

asked 2021-08-15

How many elements are in the set
{ 0, { { 0 } }?

asked 2021-08-18

Discrete Mathematics Basics

1) Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where$(a,b)\in R$ if and only if

I) everyone who has visited Web page a has also visited Web page b.

II) there are no common links found on both Web page a and Web page b.

III) there is at least one common link on Web page a and Web page b.

1) Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where

I) everyone who has visited Web page a has also visited Web page b.

II) there are no common links found on both Web page a and Web page b.

III) there is at least one common link on Web page a and Web page b.

asked 2021-08-17

1) $110001$ binary number is equivalent to which of the following decimal number

a)$48$

b)$49$

c)$59$

d)$58$

2) Which among the following is the recursive definition of Factorial, i.e., n! ?

a)$f\left(0\right)=0,\text{}f\left(n\right)=\left(n\right)f(n-1),$ where $n\in Z$ and $n\ge 1$

b)$f\left(0\right)=1,\text{}f\left(n\right)=(n+1)f(n-1),$ where $n\in Z$ and $n\ge 1$

c)$f\left(0\right)=1,\text{}f\left(n\right)=\left(n\right)f(n-1),$ where $n\in Z$ and $n\ge 1$

b)$f\left(0\right)=0,\text{}f\left(n\right)=(n+1)f(n-1),$ where $n\in Z$ and $n\ge 1$

a)

b)

c)

d)

2) Which among the following is the recursive definition of Factorial, i.e., n! ?

a)

b)

c)

b)

asked 2022-09-04

How many 5-card hands have at least two cards with the same rank?

This is a question from Zybooks Exercise 5.7.2: Counting 5-card hands from a deck of standard playing cards. I just can't wrap my head around the answer. If there is anyone that can explain this in English, that would be greatly appreciated.

How many 5-card hands have at least two cards with the same rank? Apparently the answer to this is $(}\genfrac{}{}{0ex}{}{52}{5}{\textstyle )}-{\textstyle (}\genfrac{}{}{0ex}{}{13}{5}{\textstyle )}{4}^{5$.

I see that we are using the complement rule here. I get $(}\genfrac{}{}{0ex}{}{52}{5}{\textstyle )$ denotes all the 5-card hands in a 52-card deck, but I don't see why we are subtracting $(}\genfrac{}{}{0ex}{}{13}{5}{\textstyle )}{4}^{5$.

This is a question from Zybooks Exercise 5.7.2: Counting 5-card hands from a deck of standard playing cards. I just can't wrap my head around the answer. If there is anyone that can explain this in English, that would be greatly appreciated.

How many 5-card hands have at least two cards with the same rank? Apparently the answer to this is $(}\genfrac{}{}{0ex}{}{52}{5}{\textstyle )}-{\textstyle (}\genfrac{}{}{0ex}{}{13}{5}{\textstyle )}{4}^{5$.

I see that we are using the complement rule here. I get $(}\genfrac{}{}{0ex}{}{52}{5}{\textstyle )$ denotes all the 5-card hands in a 52-card deck, but I don't see why we are subtracting $(}\genfrac{}{}{0ex}{}{13}{5}{\textstyle )}{4}^{5$.

asked 2022-07-08

Combinatorics of sports outcomes

I am trying to figure out how many possible combinations of 6 fighters can be made out of a pool of 22 fighters. These are 1v1 fights (11 fights) so I don’t want any 2 fighters fighting each other to be in the same combination. I imagine it has to be something similar to 22 choose 6 but that wouldn’t account for the fighters against each other. Order does not matter.

I am trying to figure out how many possible combinations of 6 fighters can be made out of a pool of 22 fighters. These are 1v1 fights (11 fights) so I don’t want any 2 fighters fighting each other to be in the same combination. I imagine it has to be something similar to 22 choose 6 but that wouldn’t account for the fighters against each other. Order does not matter.