Prove the generating function <munder> &#x2211;<!-- ∑ --> <mrow class="MJX-TeXAtom-ORD

Joshua Foley 2022-07-07 Answered
Prove the generating function N 0 ( M + N N ) x N = 1 ( 1 x ) M + 1
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (2)

Nirdaciw3
Answered 2022-07-08 Author has 20 answers
Step 1
You can prove it by induction.
P ( k ) : 1 ( 1 x ) m + 1 = i = 0 ( m + i i ) x i
P(0) is true, so we have 1 1 x = i = 0 x i .
Assume P(n) is true, and multiply both sides by 1 1 x .
1 ( 1 x ) m + 2 = ( j = 0 x j ) ( i = 0 ( m + i i ) x i )
i and j are independent, so the sums can be nested.
= i = 0 ( m + i i ) j = 0 x i + j
Step 2
Let i + j = k. Note that this is a different j from the previous equation, and because i 0, the new j is capped at k.
= k = 0 j = 0 k ( m + k j k j ) x k
By the hockey-stick identity and the independence of j, the inner sum can be re-written.
= k = 0 ( m + 1 + k k ) x k
Not exactly what you’re looking for?
Ask My Question
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 + + y M + 1 = N .
Then a N = ( ( M + 1 ) + N 1 ( M + 1 ) 1 ) = ( M + N M ) = ( M + N N ) .
Step 2
So N = 0 ( M + N N ) x N = N = 0 a N x N = ( k = 0 x k ) M + 1 = ( 1 1 x ) M + 1 = 1 ( 1 x ) M + 1
Not exactly what you’re looking for?
Ask My Question

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

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 (AB)C=(AC)(BC)
image

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)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.
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(0)=0, f(n)=(n)f(n1), where nZ and n1
b) f(0)=1, f(n)=(n+1)f(n1), where nZ and n1
c) f(0)=1, f(n)=(n)f(n1), where nZ and n1
b) f(0)=0, f(n)=(n+1)f(n1), where nZ and n1
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 ( 52 5 ) ( 13 5 ) 4 5 .
I see that we are using the complement rule here. I get ( 52 5 ) denotes all the 5-card hands in a 52-card deck, but I don't see why we are subtracting ( 13 5 ) 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.

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question