Solving recurrence relations

CS 207m: Discrete Structures (Minor)

Lecture 10 – Counting and Combinatorics Solving Recurrence relations via generating functions

Feb 14 2018

Last few classes

Basic counting techniques and applications

1. Sum and product, bijection, double counting principles 2. Binomial coefficients and binomial theorem, Pascal’s

triangle

3. Permutations and combinations with/without repetitions 4. Counting subsets, relations, Handshake lemma

5. Stirling’s approximation: Estimating n!

6. Recurrence relations and one method to solve them.

Today

Solving recurrence relations via generating functions.

Last few classes

Basic counting techniques and applications

1. Sum and product, bijection, double counting principles 2. Binomial coefficients and binomial theorem, Pascal’s

triangle

3. Permutations and combinations with/without repetitions 4. Counting subsets, relations, Handshake lemma

5. Stirling’s approximation: Estimating n!

6. Recurrence relations and one method to solve them.

Today

Solving recurrence relations via generating functions.

Solving recurrence relations

By solving, we mean give a closed-form expression forn^th term.

Fibonacci recurrence: ∀n ≥2,F_n=Fn−1+Fn−2, F₀ =F₁ = 1.

Proof method 1 (for linear recurrences: tryF_n =αⁿ!) 1. αⁿ=αⁿ⁻¹+αⁿ⁻² implies αⁿ⁻²(α²−α−1) = 0. 2. So if α²−α−1 = 0, the recurrence holds for alln. 3. Solving, α= ¹⁺

√5

2 , β= ¹⁻

√5 2

4. Thus, general solution is Fn=a(¹⁺

√5

2 )ⁿ+b(¹⁻

√5 2 )ⁿ. 5. Use F₀ and F₁ – initial conditions: a=

√ 5+1 2√

5 ,b=

√5−1 2√

5

Thus,Fn=

√ 5+1 2√

5 (¹⁺

√ 5 2 )ⁿ+

√5−1 2√

5 (¹⁻

√ 5 2 )ⁿ.

But this method may not work if we have repeated roots (but this can be fixed) and non-linear recurrences.

Solving recurrence relations

By solving, we mean give a closed-form expression forn^th term.

Fibonacci recurrence: ∀n ≥2,F_n=Fn−1+Fn−2, F₀ =F₁ = 1.

Proof method 1 (for linear recurrences: tryF_n =αⁿ!) 1. αⁿ=αⁿ⁻¹+αⁿ⁻² implies αⁿ⁻²(α²−α−1) = 0. 2. So if α²−α−1 = 0, the recurrence holds for alln. 3. Solving, α= ¹⁺

√5

2 , β= ¹⁻

√5 2

4. Thus, general solution is Fn=a(¹⁺

√5

2 )ⁿ+b(¹⁻

√5 2 )ⁿ. 5. Use F₀ and F₁ – initial conditions: a=

√ 5+1 2√

5 ,b=

√5−1 2√

5

Thus,Fn=

√ 5+1 2√

5 (¹⁺

√ 5 2 )ⁿ+

√5−1 2√

5 (¹⁻

√ 5 2 )ⁿ.

But this method may not work if we have repeated roots (but this can be fixed) and non-linear recurrences.

Solving recurrence relations

By solving, we mean give a closed-form expression forn^th term.

Fibonacci recurrence: ∀n ≥2,F_n=Fn−1+Fn−2, F₀ =F₁ = 1.

Proof method 1 (for linear recurrences: tryF_n =αⁿ!) 1. αⁿ=αⁿ⁻¹+αⁿ⁻² impliesαⁿ⁻²(α²−α−1) = 0.

2. So if α²−α−1 = 0, the recurrence holds for alln.

3. Solving, α= ¹⁺

√5

2 , β= ¹⁻

√5 2

4. Thus, general solution is Fn=a(¹⁺

√5

2 )ⁿ+b(¹⁻

√5 2 )ⁿ. 5. Use F₀ and F₁ – initial conditions: a=

√ 5+1 2√

5 ,b=

√5−1 2√

5

Thus,Fn=

√ 5+1 2√

5 (¹⁺

√ 5 2 )ⁿ+

√5−1 2√

5 (¹⁻

√ 5 2 )ⁿ.

But this method may not work if we have repeated roots (but this can be fixed) and non-linear recurrences.

Solving recurrence relations

By solving, we mean give a closed-form expression forn^th term.

Fibonacci recurrence: ∀n ≥2,F_n=Fn−1+Fn−2, F₀ =F₁ = 1.

Proof method 1 (for linear recurrences: tryF_n =αⁿ!) 1. αⁿ=αⁿ⁻¹+αⁿ⁻² impliesαⁿ⁻²(α²−α−1) = 0.

2. So if α²−α−1 = 0, the recurrence holds for alln.

3. Solving, α= ¹⁺

√5

2 , β= ¹⁻

√5 2

4. Thus, general solution is Fn=a(¹⁺

√5

2 )ⁿ+b(¹⁻

√5 2 )ⁿ. 5. Use F₀ and F₁ – initial conditions: a=

√ 5+1 2√

5 ,b=

√5−1 2√

5

√ √ √ √

But this method may not work if we have repeated roots (but this can be fixed) and non-linear recurrences.

Solving recurrence relations

By solving, we mean give a closed-form expression forn^th term.

Fibonacci recurrence: ∀n ≥2,F_n=Fn−1+Fn−2, F₀ =F₁ = 1.

Proof method 1 (for linear recurrences: tryF_n =αⁿ!) 1. αⁿ=αⁿ⁻¹+αⁿ⁻² impliesαⁿ⁻²(α²−α−1) = 0.

2. So if α²−α−1 = 0, the recurrence holds for alln.

3. Solving, α= ¹⁺

√5

2 , β= ¹⁻

√5 2

4. Thus, general solution is Fn=a(¹⁺

√5

2 )ⁿ+b(¹⁻

√5 2 )ⁿ. 5. Use F₀ and F₁ – initial conditions: a=

√ 5+1 2√

5 ,b=

√5−1 2√

5

Thus,Fn=

√ 5+1 2√

5 (¹⁺

√ 5 2 )ⁿ+

√5−1 2√

5 (¹⁻

√ 5 2 )ⁿ.

But this method may not work if we have repeated roots (but this can be fixed) and non-linear recurrences.

Proof Method 2: Using generating functions

Fibonacci recurrence relation

Forn≥2,Fn=Fn−1+Fn−2,F0 =F1 = 1.

ComputeF_n in terms ofn.

I Consider the power series... φ(t) =

∞

X

n=0

F(n)tⁿ.

Proof Method 2: Using generating functions

Fibonacci recurrence relation

Forn≥2,Fn=Fn−1+Fn−2,F0 =F1 = 1.

ComputeF_n in terms ofn.

I Consider the power series... φ(t) =

∞

X

n=0

F(n)tⁿ.

tφ(t) =

∞

X

n=0

F(n)tⁿ⁺¹ =

∞

X

n=1

F(n−1)tⁿ

Proof Method 2: Using generating functions

Fibonacci recurrence relation

Forn≥2,Fn=Fn−1+Fn−2,F0 =F1 = 1.

ComputeF_n in terms ofn.

I Consider the power series... φ(t) =

∞

X

n=0

F(n)tⁿ.

tφ(t) =

∞

X

n=0

F(n)tⁿ⁺¹ =

∞

X

n=1

F(n−1)tⁿ

t²φ(t) =

∞

X

n=0

F(n)tⁿ⁺² =

∞

X

n=2

F(n−2)tⁿ

Proof Method 2: Using generating functions

Fibonacci recurrence relation

Forn≥2,F_n=Fn−1+Fn−2,F₀ =F₁ = 1.

ComputeFn in terms ofn.

I Consider the power series... φ(t) =

∞

X

n=0

F(n)tⁿ.

tφ(t) =

∞

X

n=0

F(n)tⁿ⁺¹ =

∞

X

n=1

F(n−1)tⁿ

t²φ(t) =

∞

X

n=0

F(n)tⁿ⁺² =

∞

X

n=2

F(n−2)tⁿ

(t+t²)φ(t) =

∞

X

n=0

F(n)tⁿ−1 (t+t²)φ(t) =φ(t)−1

Proof Method 2: Using generating functions

I φ(t) = _1−t−t¹ 2

= (1−αt)(1−βt)¹ = _1−αt^a +_1−βt^b

I Solving we getα= ¹⁺

√ 5

2 , β= ¹⁻

√ 5 2 , a=

√ 5+1 2√

5 , b=

√5−1 2√

5 I Now φ(t) =a(1 +αt+α²t²+. . .) +b(1 +βt+β²t²+. . .)

I Equating coefficients oftⁿ we get F_n=aαⁿ+bβⁿ. thus, as before

F(n) =

√5 + 1 2√

5

1 +√ 5 2

!n

+

√5−1 2√

5

1−√ 5 2

!n

Proof Method 2: Using generating functions

I φ(t) = _1−t−t¹ 2= (1−αt)(1−βt)¹

= _1−αt^a +_1−βt^b

I Solving we getα= ¹⁺

√ 5

2 , β= ¹⁻

√ 5 2 , a=

√ 5+1 2√

5 , b=

√5−1 2√

5 I Now φ(t) =a(1 +αt+α²t²+. . .) +b(1 +βt+β²t²+. . .)

I Equating coefficients oftⁿ we get F_n=aαⁿ+bβⁿ. thus, as before

F(n) =

√5 + 1 2√

5

1 +√ 5 2

!n

+

√5−1 2√

5

1−√ 5 2

!n

Proof Method 2: Using generating functions

I φ(t) = _1−t−t¹ 2= (1−αt)(1−βt)¹ = _1−αt^a +_1−βt^b

I Solving we getα= ¹⁺

√5

2 , β= ¹⁻

√5 2 , a=

√5+1 2√

5 , b=

√5−1 2√

5

I Now φ(t) =a(1 +αt+α²t²+. . .) +b(1 +βt+β²t²+. . .)

I Equating coefficients oftⁿ we get F_n=aαⁿ+bβⁿ. thus, as before

F(n) =

√5 + 1 2√

5

1 +√ 5 2

!n

+

√5−1 2√

5

1−√ 5 2

!n

Proof Method 2: Using generating functions

I φ(t) = _1−t−t¹ 2= (1−αt)(1−βt)¹ = _1−αt^a +_1−βt^b

I Solving we getα= ¹⁺

√5

2 , β= ¹⁻

√5 2 , a=

√5+1 2√

5 , b=

√5−1 2√

5 I Now φ(t) =a(1 +αt+α²t²+. . .) +b(1 +βt+β²t²+. . .)

I Equating coefficients oftⁿ we get F_n=aαⁿ+bβⁿ. thus, as before

F(n) =

√5 + 1 2√

5

1 +√ 5 2

!n

+

√5−1 2√

5

1−√ 5 2

!n

Proof Method 2: Using generating functions

I φ(t) = _1−t−t¹ 2= (1−αt)(1−βt)¹ = _1−αt^a +_1−βt^b

I Solving we getα= ¹⁺

√5

2 , β= ¹⁻

√5 2 , a=

√5+1 2√

5 , b=

√5−1 2√

5 I Now φ(t) =a(1 +αt+α²t²+. . .) +b(1 +βt+β²t²+. . .)

I Equating coefficients oftⁿ we get F_n=aαⁿ+bβⁿ.

thus, as before F(n) =

√5 + 1 2√

5

1 +√ 5 2

!n

+

√5−1 2√

5

1−√ 5 2

!n

Proof Method 2: Using generating functions

I φ(t) = _1−t−t¹ 2= (1−αt)(1−βt)¹ = _1−αt^a +_1−βt^b

I Solving we getα= ¹⁺

√5

2 , β= ¹⁻

√5 2 , a=

√5+1 2√

5 , b=

√5−1 2√

5 I Now φ(t) =a(1 +αt+α²t²+. . .) +b(1 +βt+β²t²+. . .)

I Equating coefficients oftⁿ we get F_n=aαⁿ+bβⁿ. thus, as before

F(n) =

√5 + 1 2√

5

1 +√ 5 2

!n

+

√5−1 2√

5

1−√ 5 2

!n

Properties of generating functions

Definition

The(ordinary) generating function for a sequencea0, a1, . . .∈R is the infinite seriesφ(x) =P∞

k=0a_kx^k.

I Let f(x) =P∞

k=0a_kx^k,g(x) =P∞

k=0b_kx^k. Then 1. Iff(x) =g(x), thenak=bk for allk.

2. f(x) +g(x) =P∞

k=0(ak+bk)x^k, 3. f(x)g(x) =P∞

k=0(Pk

j=0ajbk−j)x^k, 4. _dx^d (P∞

k=0akx^k) =P∞

k=1(kak)x^k−1

I Let u∈R,k∈Z^≥0, Thenextended binomial coefficient ^u_k is defined as ^u_k

= u(u−1)...(u−k+1)

k! ifk >0 and = 1 ifk= 0.

I What if u=−nforn∈N? The extended binomial theorem Letu∈R, (1 +x)^u =P∞

k=0 u k

x^k. If you don’t like this, takex∈R,|x|<1.

Properties of generating functions

Definition

The(ordinary) generating function for a sequencea0, a1, . . .∈R is the infinite seriesφ(x) =P∞

k=0a_kx^k.

I Let f(x) =P∞

k=0a_kx^k,g(x) =P∞

k=0b_kx^k. Then 1. Iff(x) =g(x), thenak=bk for allk.

2. f(x) +g(x) =P∞

k=0(ak+bk)x^k, 3. f(x)g(x) =P∞

k=0(Pk

j=0ajbk−j)x^k, 4. _dx^d (P∞

k=0akx^k) =P∞

k=1(kak)x^k−1

I Let u∈R,k∈Z^≥0, Thenextended binomial coefficient ^u_k is defined as ^u_k

= u(u−1)...(u−k+1)

k! ifk >0 and = 1 ifk= 0.

I What if u=−nforn∈N?

The extended binomial theorem Letu∈R, (1 +x)^u =P∞

k=0 u k

x^k. If you don’t like this, takex∈R,|x|<1.

Properties of generating functions

Definition

The(ordinary) generating function for a sequencea0, a1, . . .∈R is the infinite seriesφ(x) =P∞

k=0a_kx^k.

I Let f(x) =P∞

k=0a_kx^k,g(x) =P∞

k=0b_kx^k. Then 1. Iff(x) =g(x), thenak=bk for allk.

2. f(x) +g(x) =P∞

k=0(ak+bk)x^k, 3. f(x)g(x) =P∞

k=0(Pk

j=0ajbk−j)x^k, 4. _dx^d (P∞

k=0akx^k) =P∞

k=1(kak)x^k−1

I Let u∈R,k∈Z^≥0, Thenextended binomial coefficient ^u_k is defined as ^u_k

= u(u−1)...(u−k+1)

k! ifk >0 and = 1 ifk= 0.

I What if u=−nforn∈N?

If you don’t like this, takex∈R,|x|<1.

Properties of generating functions

Definition

The(ordinary) generating function for a sequencea0, a1, . . .∈R is the infinite seriesφ(x) =P∞

k=0a_kx^k.

I Let f(x) =P∞

k=0a_kx^k,g(x) =P∞

k=0b_kx^k. Then 1. Iff(x) =g(x), thenak=bk for allk.

2. f(x) +g(x) =P∞

k=0(ak+bk)x^k, 3. f(x)g(x) =P∞

k=0(Pk

j=0ajbk−j)x^k, 4. _dx^d (P∞

k=0akx^k) =P∞

k=1(kak)x^k−1

I Let u∈R,k∈Z^≥0, Thenextended binomial coefficient ^u_k is defined as ^u_k

= u(u−1)...(u−k+1)

k! ifk >0 and = 1 ifk= 0.

I What if u=−nforn∈N? The extended binomial theorem Letu∈R, (1 +x)^u =P∞

k=0 u k

x^k. If you don’t like this, takex∈R,|x|<1.

Simple examples using generating functions

Standard identities:

I 1

1−ax =P∞ k=0a^kx^k

I 1

1−x^r =P∞ k=0x^rk

I e^x=P∞ k=0x^k

k!

Class work:

1. Solve the recurrencea_k= 4ak−1 witha0= 3. 2. Solve the recurrenceak= 8ak−1+ 10^k−1 with

a₀ = 1, a₁ = 9.

Simple examples using generating functions

Standard identities:

I 1

1−ax =P∞ k=0a^kx^k

I 1

1−x^r =P∞ k=0x^rk

I e^x=P∞ k=0x^k

k!

Class work:

1. Solve the recurrencea_k= 4ak−1 witha₀= 3.

2. Solve the recurrenceak= 8ak−1+ 10^k−1 with a₀ = 1, a₁ = 9.

Simple examples using generating functions

Standard identities:

I 1

1−ax =P∞ k=0a^kx^k

I 1

1−x^r =P∞ k=0x^rk

I e^x=P∞ k=0x^k

k!

Class work:

1. Solve the recurrencea_k= 4ak−1 witha₀= 3.

2. Solve the recurrencea_k= 8ak−1+ 10^k−1 with a₀ = 1, a₁ = 9.

Solving Catalan numbers using generating functions

Catalan Numbers C(n) =

n−1

X

i=1

C(i)C(n−i) for n >1,C(0) = 0, C(1) = 1.

Solving Catalan numbers using generating functions

Catalan Numbers C(n) =

n−1

X

i=1

C(i)C(n−i) for n >1,C(0) = 0, C(1) = 1.

I Let φ(x) =P∞

k=1C(k)x^k.

Solving Catalan numbers using generating functions

Catalan Numbers C(n) =

n−1

X

i=1

C(i)C(n−i) for n >1,C(0) = 0, C(1) = 1.

I Let φ(x) =P∞

k=1C(k)x^k.

I Now considerφ(x)².

I φ(x)² = (P∞

k=1C(k)x^k)(P∞

k=1C(k)x^k)

= (P∞ k=2

Pk−1

i=1 C(i)C(k−i)x^k)

= (P∞

k=2C(k)x^k) =φ(x)−x

Solving Catalan numbers using generating functions

Catalan Numbers C(n) =

n−1

X

i=1

C(i)C(n−i) for n >1,C(0) = 0, C(1) = 1.

I Let φ(x) =P∞

k=1C(k)x^k.

I Now considerφ(x)².

I φ(x)² = (P∞

k=1C(k)x^k)(P∞

k=1C(k)x^k)

= (P∞ k=2

Pk−1

i=1 C(i)C(k−i)x^k)

= (P∞

k=2C(k)x^k) =φ(x)−x

I Solving for φ(x) we get, φ(x) = ¹₂(1±(1−4x)^1/2)

I But since φ(0) = 0, we have

1 1/2 1 1 1/2

Catalan numbers

Recall: Extended binomial theorem Letα∈R,(1 +x)^α=P∞

n=0 α n

xⁿ, where ^α_n

= α(α−1)...(α−n+1)

n! .

Catalan numbers

Recall: Extended binomial theorem Letα∈R,(1 +x)^α=P∞

n=0 α n

xⁿ, where ^α_n

= α(α−1)...(α−n+1)

n! .

I P∞

k=1C(k)x^k=φ(x) = ¹₂ + (−¹₂(1−4x)^1/2) =

1

2 + (−¹₂P∞ k=0

1/2 k

(−4x)^k).

Catalan numbers

Recall: Extended binomial theorem Letα∈R,(1 +x)^α=P∞

n=0 α n

xⁿ, where ^α_n

= α(α−1)...(α−n+1)

n! .

I P∞

k=1C(k)x^k=φ(x) = ¹₂ + (−¹₂(1−4x)^1/2) =

1

2 + (−¹₂P∞ k=0

1/2 k

(−4x)^k).

I The coefficient of x^k is C(k) =−¹₂ ^1/2_k (−4)^k

=−¹₂(¹₂(¹₂−1)(¹₂ −2). . .(¹₂ −k+ 1))⁽⁻⁴⁾_k!^k

=−¹₂(¹₂)(−³₂)(−⁵₂). . .(−^2k−3₂ ))⁽⁻⁴⁾_k!^k

Catalan numbers

Recall: Extended binomial theorem Letα∈R,(1 +x)^α=P∞

n=0 α n

xⁿ, where ^α_n

= α(α−1)...(α−n+1)

n! .

I P∞

k=1C(k)x^k=φ(x) = ¹₂ + (−¹₂(1−4x)^1/2) =

1

2 + (−¹₂P∞ k=0

1/2 k

(−4x)^k).

I The coefficient of x^k is C(k) =−¹₂ ^1/2_k (−4)^k

=−¹₂(¹₂(¹₂−1)(¹₂ −2). . .(¹₂ −k+ 1))⁽⁻⁴⁾_k!^k

=−¹₂(¹₂)(−³₂)(−⁵₂). . .(−^2k−3₂ ))⁽⁻⁴⁾_k!^k

I C(k) =⁽⁻¹⁾_2k+1^k(−4)_k! ^k ·1·3· · ·(2k−3)

Catalan numbers

Recall: Extended binomial theorem Letα∈R,(1 +x)^α=P∞

n=0 α n

xⁿ, where ^α_n

= α(α−1)...(α−n+1)

n! .

I P∞

k=1C(k)x^k=φ(x) = ¹₂ + (−¹₂(1−4x)^1/2) =

1

2 + (−¹₂P∞ k=0

1/2 k

(−4x)^k).

I The coefficient of x^k is C(k) =−¹₂ ^1/2_k (−4)^k

=−¹₂(¹₂(¹₂−1)(¹₂ −2). . .(¹₂ −k+ 1))⁽⁻⁴⁾_k!^k

=−¹₂(¹₂)(−³₂)(−⁵₂). . .(−^2k−3₂ ))⁽⁻⁴⁾_k!^k

I C(k) =⁽⁻¹⁾_2k+1^k(−4)_k! ^k ·1·3· · ·(2k−3)

I C(k) =₂k+1^1·4k·k!·1.2....(2k−3)(2k−2)

2^k−1(k−1)! = _k!(k−1)!^(2k−2)!.

Catalan numbers

Recall: Extended binomial theorem Letα∈R,(1 +x)^α=P∞

n=0 α n

xⁿ, where ^α_n

= α(α−1)...(α−n+1)

n! .

I P∞

k=1C(k)x^k=φ(x) = ¹₂ + (−¹₂(1−4x)^1/2) =

1

2 + (−¹₂P∞ k=0

1/2 k

(−4x)^k).

I The coefficient of x^k is C(k) =−¹₂ ^1/2_k (−4)^k

=−¹₂(¹₂(¹₂−1)(¹₂ −2). . .(¹₂ −k+ 1))⁽⁻⁴⁾_k!^k

=−¹₂(¹₂)(−³₂)(−⁵₂). . .(−^2k−3₂ ))⁽⁻⁴⁾_k!^k

I C(k) =⁽⁻¹⁾_2k+1^k(−4)_k! ^k ·1·3· · ·(2k−3)

I C(k) =_2k+1^1·4k_·k!·1.2....(2k−3)(2k−2)

2^k−1(k−1)! = _k!(k−1)!^(2k−2)!.

Other applications of generating functions

I What is the number of ways a_k of selecting kelements from an nelement set if repetitions are allowed?

I Letφ(x) =P∞ k=0akx^k.

I Observe thatφ(x) = (1 +x+x²+. . .)ⁿ= (1−x)⁻ⁿ

I Expand this by the extended binomial theorem and compare coefficients ofx^k.

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

I (H.W)What if there must be ≥1 element of each type?

I Proving binomial identities: Show thatPn k=0

n k

2

= ²ⁿ_n .

I Compare coefficients ofxⁿ in (1 +x)²ⁿ= ((1 +x)ⁿ)².

Other applications of generating functions

I What is the number of ways a_k of selecting kelements from an nelement set if repetitions are allowed?

I Letφ(x) =P∞ k=0akx^k.

I Observe thatφ(x) = (1 +x+x²+. . .)ⁿ= (1−x)⁻ⁿ

I Expand this by the extended binomial theorem and compare coefficients ofx^k.

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

I (H.W)What if there must be ≥1 element of each type?

I Proving binomial identities: Show thatPn k=0

n k

2

= ²ⁿ_n .

I Compare coefficients ofxⁿ in (1 +x)²ⁿ= ((1 +x)ⁿ)².

Other applications of generating functions

I What is the number of ways a_k of selecting kelements from an nelement set if repetitions are allowed?

I Letφ(x) =P∞ k=0akx^k.

I Observe thatφ(x) = (1 +x+x²+. . .)ⁿ= (1−x)⁻ⁿ

I Expand this by the extended binomial theorem and compare coefficients ofx^k.

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

I (H.W)What if there must be ≥1 element of each type?

I Proving binomial identities: Show thatPn k=0

n k

2

= ²ⁿ_n .

I Compare coefficients ofxⁿ in (1 +x)²ⁿ= ((1 +x)ⁿ)².

Other applications of generating functions

I What is the number of ways a_k of selecting kelements from an nelement set if repetitions are allowed?

I Letφ(x) =P∞ k=0akx^k.

I Observe thatφ(x) = (1 +x+x²+. . .)ⁿ= (1−x)⁻ⁿ

I Expand this by the extended binomial theorem and compare coefficients ofx^k.

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

I (H.W)What if there must be ≥1 element of each type?

I Proving binomial identities: Show thatPn k=0

n k

2

= ²ⁿ_n .

I Compare coefficients ofxⁿ in (1 +x)²ⁿ= ((1 +x)ⁿ)².

Other applications of generating functions

I What is the number of ways a_k of selecting kelements from an nelement set if repetitions are allowed?

I Letφ(x) =P∞ k=0akx^k.

I Observe thatφ(x) = (1 +x+x²+. . .)ⁿ= (1−x)⁻ⁿ

I Expand this by the extended binomial theorem and compare coefficients ofx^k.

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

I (H.W)What if there must be ≥1 element of each type?

I Proving binomial identities: Show thatPn k=0

n k

2

= ²ⁿ_n .

I Compare coefficients ofxⁿ in (1 +x)²ⁿ= ((1 +x)ⁿ)².

Other applications of generating functions

I What is the number of ways a_k of selecting kelements from an nelement set if repetitions are allowed?

I Letφ(x) =P∞ k=0akx^k.

I Observe thatφ(x) = (1 +x+x²+. . .)ⁿ= (1−x)⁻ⁿ

I Expand this by the extended binomial theorem and compare coefficients ofx^k.

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

I (H.W)What if there must be ≥1 element of each type?

I Proving binomial identities: Show thatPn k=0

n k

2

= ²ⁿ_n .

I Compare coefficients ofxⁿ in (1 +x)²ⁿ= ((1 +x)ⁿ)².

Other applications of generating functions

I What is the number of ways a_k of selecting kelements from an nelement set if repetitions are allowed?

I Letφ(x) =P∞ k=0akx^k.

I Observe thatφ(x) = (1 +x+x²+. . .)ⁿ= (1−x)⁻ⁿ

I Expand this by the extended binomial theorem and compare coefficients ofx^k.

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

I (H.W)What if there must be ≥1 element of each type?

I Proving binomial identities: Show thatPn k=0

n k

2

= ²ⁿ_n .

I Compare coefficients ofxⁿ in (1 +x)²ⁿ= ((1 +x)ⁿ)².

Other applications of generating functions

I What is the number of ways a_k of selecting kelements from an nelement set if repetitions are allowed?

I Letφ(x) =P∞ k=0akx^k.

I Observe thatφ(x) = (1 +x+x²+. . .)ⁿ= (1−x)⁻ⁿ

I Expand this by the extended binomial theorem and compare coefficients ofx^k.

I a_k= ⁻ⁿ_k

(−1)^k = (−1)^{k n+k−1}_k

(−1)^k= ^n+k−1_k .

I (H.W)What if there must be ≥1 element of each type?

I Proving binomial identities: Show thatPn k=0

n k

2

= ²ⁿ_n .

I Compare coefficients ofxⁿ in (1 +x)²ⁿ= ((1 +x)ⁿ)².