Formal Series Slides Formal Series Foundations
Lesson 1: Transforming sequences into algebraic blueprints
The Algebraic Magic
What if we could turn an infinite list of numbers into a single polynomial ?
Sequence: \( (1, 1, 1, 1, \dots) \)
Function: \( \frac{1}{1-x} \)
Formal Power Series
"A Generating Function is a clothesline on which we hang up a sequence of numbers for display."
— Herbert Wilf
Formal Definitions
Ordinary Generating Function (OGF)
\( A(x) = \sum_{n=0}^{\infty} a_n x^n \)
The Sequence
\( \{a_n\}_{n \ge 0} = (a_0, a_1, a_2, \dots) \)
The Variable
\( x \) is a placeholder . We do not care about convergence here.
The Ring \( R[[x]] \)
Addition
\( A(x) + B(x) = \sum (a_n + b_n)x^n \)
Multiplication (Cauchy)
\( A(x)B(x) = \sum_{n} \left( \sum_{k=0}^n a_k b_{n-k} \right) x^n \)
Crucial Property
An element \( A(x) \) is invertible if and only if \( a_0 \neq 0 \) in the base ring.
This allows us to treat \( \frac{1}{1-x} \) purely as the inverse of \( (1-x) \).
Essential Blueprints
Sequence Generating Function \( (1, 1, 1, \dots) \) \( 1/(1-x) \) \( (1, 2, 3, 4, \dots) \) \( 1/(1-x)^2 \) \( (1, c, c^2, \dots) \) \( 1/(1-cx) \) \( \binom{n}{k} \) (fixed \( n \)) \( (1+x)^n \)
Formal Foundations Handout Formal Foundations Handout
Lesson 1: Algebraic Operations on Power Series
NAME:
DATE:
Core Properties
Cauchy Product:
\( [x^n] A(x)B(x) = \sum_{k=0}^n a_k b_{n-k} \)
Inversion:
\( B(x) = A(x)^{-1} \iff a_0 b_0 = 1 \text{ and } \sum_{k=0}^n a_k b_{n-k} = 0 \text{ for } n > 0 \)
1. Sequence Encoding
Find the Ordinary Generating Function (OGF) for the following sequences. Express in closed form where possible.
a)
\( a_n = 3^n + (-2)^n \)
b)
\( b_n = n \) (Hint: Consider the derivative of the geometric series)
2. The Power of Multiplication
Let \( A(x) = \sum_{n=0}^{\infty} x^n \) and \( B(x) = \sum_{n=0}^{\infty} (n+1)x^n \). Find the coefficient of \( x^n \) in the product \( C(x) = A(x)B(x) \).
Show your sum and simplify the result using binomial identity: \( \sum_{k=0}^n \binom{k}{r} = \binom{n+1}{r+1} \)
3. Structural Inverses
Prove that the sequence \( a_n = 1 \) for all \( n \) has the formal inverse \( B(x) = 1 - x \). Verify this using the coefficient identity \( \sum_{k=0}^n a_k b_{n-k} = \delta_{n,0} \).
4. Composition of Series (Challenge)
Given \( F(x) = \sum f_n x^n \) and \( G(x) = \sum g_n x^n \). Under what condition on \( G(x) \) is the composition \( F(G(x)) \) a well-defined formal power series?
If \( F(x) = e^x = \sum \frac{x^n}{n!} \) and \( G(x) = \ln(1+x) = \sum (-1)^{n-1} \frac{x^n}{n} \), find the first three terms of \( F(G(x)) \).
Series Architect Teacher Guide Series Architect Teacher Guide
Lesson 1: Formal Power Series Fundamentals
Instructional Focus
The primary goal of this lesson is to decouple the concept of a power series from its analytical behavior (convergence). Graduate students often struggle to "unlearn" calculus constraints. Emphasize that \( x \) is an indeterminate , and our operations are strictly algebraic.
Key Misconceptions
Radius of Convergence: Students may try to find it. Remind them that in the ring \( R[[x]] \), convergence is defined with respect to the \( (x) \)-adic topology, not the real line.Division: Students might divide by zero. Remind them that \( A(x) \) is invertible iff \( a_0 \neq 0 \).
Lesson Flow
1 The Hook: Introduce the "Clothesline" metaphor.
2 Workshop: Derive the Cauchy Product.
3 Inquiry: Challenge students to find the inverse of \( (1-x) \).
4 Practice: Complete the "Formal Foundations" handout.
Handout Answer Key
1. Sequence Encoding
Solution a
\( A(x) = \frac{1}{1-3x} + \frac{1}{1+2x} \)
Combined: \( \frac{2-x}{(1-3x)(1+2x)} \)
Solution b
\( B(x) = x \frac{d}{dx} \sum x^n = x \frac{d}{dx} \frac{1}{1-x} \)
Result: \( \frac{x}{(1-x)^2} \)
2. Cauchy Product
Let \( A(x) = \sum x^n \) and \( B(x) = \sum (n+1)x^n \).
\( c_n = \sum_{k=0}^n a_{n-k}b_k = \sum_{k=0}^n (1)(k+1) \)
\( c_n = 1 + 2 + \dots + (n+1) = \frac{(n+1)(n+2)}{2} = \binom{n+2}{2} \)
Connection: This is the series for \( \frac{1}{(1-x)^3} \).
3. Structural Inverses
Verification for \( n=0 \): \( a_0 b_0 = 1 \cdot 1 = 1 \). Correct.
Verification for \( n=1 \): \( a_1 b_0 + a_0 b_1 = 1(1) + 1(-1) = 0 \). Correct.
Verification for \( n>1 \): \( \sum_{k=0}^n a_{n-k} b_k = a_n b_0 + a_{n-1} b_1 = 1(1) + 1(-1) = 0 \). Correct.
4. Composition Challenge
Condition: \( g_0 = 0 \). Otherwise, the constant term of the result would be an infinite sum of constants, which is not defined formally.
First 3 Terms: \( F(G(x)) = e^{\ln(1+x)} = 1+x \). The coefficients are \( 1, 1, 0, 0, \dots \)
Recurrence Resolver Slides Recurrence Resolution Path
Lesson 2: From Recursive Definitions to Closed Forms
The Efficiency Problem
The Recursive Way
\( F_{1000} = F_{999} + F_{998} \)
(Requires 999 previous steps)
The Closed-Form Way
\( F_n = \frac{1}{\sqrt{5}} \left( \phi^n - \psi^n \right) \)
(Calculate immediately for any \( n \))
The Method of Generating Functions
1. Define the Series
Write \( A(x) = \sum_{n=0}^{\infty} a_n x^n \).
2. Multiply and Sum
Apply the recurrence to the sum over \( n \).
3. Solve for \( A(x) \)
Isolate \( A(x) \) as a rational function.
4. Extract Coefficients
Use Partial Fractions to find \( a_n \).
Visualizing Step 2
\( a_n = c_1 a_{n-1} + c_2 a_{n-2} \)
The Fibonacci Derivation
Algebraic Setup
\( A(x) = x + x A(x) + x^2 A(x) \)
Denominator Roots
\( 1-x-x^2 = (1-\phi x)(1-\psi x) \)
Partial Fraction Result:
\( \frac{x}{(1-\phi x)(1-\psi x)} = \frac{1}{\sqrt{5}} \left( \frac{1}{1-\phi x} - \frac{1}{1-\psi x} \right) \)
The Magic of Linearity
The denominator of the GF is the characteristic polynomial in disguise.
If the recurrence is \( a_n = c_1 a_{n-1} + c_2 a_{n-2} \), then the GF denominator is \( 1 - c_1 x - c_2 x^2 \).
Roots of the polynomial give the basis functions of the sequence.
Takeaway
Generating functions solve recurrences not by "guessing and checking," but by performing a basis transformation in the ring of power series.
Fibonacci Formula Worksheet Fibonacci Formula Worksheet
Lesson 2: Linear Recurrences
NAME
1
The Recurrence Transform
Given the recurrence \( a_n = 5a_{n-1} - 6a_{n-2} \) for \( n \ge 2 \), with initial conditions \( a_0 = 1, a_1 = 4 \). Define \( A(x) = \sum_{n=0}^{\infty} a_n x^n \).
Step: Write the equation for \( A(x) \) by summing the recurrence.
2
Partial Fraction Extraction
You should have arrived at \( A(x) = \frac{1-x}{1-5x+6x^2} \). Factor the denominator and decompose \( A(x) \) into partial fractions.
3
The General Formula
Extract the coefficient of \( x^n \) from your partial fractions to find the closed-form expression for \( a_n \).
4
Advanced: Non-Homogeneous Cases
Consider the recurrence \( a_n = 2a_{n-1} + n \) with \( a_0 = 1 \). How does the "extra term" \( n \) affect the generating function?
Hint: The OGF for \( n \) is \( \frac{x}{(1-x)^2} \). Add this to your algebraic setup.
Self-Reflection Question: In what way does the denominator of the GF change when a recurrence becomes non-homogeneous?
Partial Fraction Master Key Partial Fraction Master Key
Lesson 2: Linear Recurrences Answer Key
Problem 1: The Transform
Recurrence: \( a_n - 5a_{n-1} + 6a_{n-2} = 0 \)
Multiply by \( x^n \) and sum for \( n \ge 2 \):
\( (A(x) - a_0 - a_1 x) - 5x(A(x) - a_0) + 6x^2 A(x) = 0 \)
Substitute \( a_0 = 1, a_1 = 4 \):
\( A(x) - 1 - 4x - 5x A(x) + 5x + 6x^2 A(x) = 0 \)
\( A(x)(1 - 5x + 6x^2) = 1 - x \)
\( A(x) = \frac{1-x}{1-5x+6x^2} \)
Problem 2: Decomposition
Denominator: \( 1 - 5x + 6x^2 = (1-2x)(1-3x) \)
Setup: \( \frac{1-x}{(1-2x)(1-3x)} = \frac{A}{1-2x} + \frac{B}{1-3x} \)
Solve for A (set \( x = 1/2 \)): \( A = \frac{1-1/2}{1-3/2} = \frac{1/2}{-1/2} = -1 \)
Solve for B (set \( x = 1/3 \)): \( B = \frac{1-1/3}{1-2/3} = \frac{2/3}{1/3} = 2 \)
Decomposition: \( A(x) = \frac{2}{1-3x} - \frac{1}{1-2x} \)
Problem 3: Final Form
Using the geometric series formula \( \frac{1}{1-cx} = \sum c^n x^n \):
\( A(x) = 2 \sum (3x)^n - \sum (2x)^n \)
\( A(x) = \sum [2(3^n) - 2^n] x^n \)
Closed Form: \( a_n = 2 \cdot 3^n - 2^n \)
Advanced: Non-Homogeneous Result
For \( a_n = 2a_{n-1} + n \), the resulting generating function is:
\( A(x) = \frac{1 - 2x + 2x^2}{(1-2x)(1-x)^2} \)
Extracting coefficients requires a partial fraction with a repeated root \( (1-x)^2 \).
Result: \( a_n = 3 \cdot 2^n - n - 2 \)
Combinatorial Coin Slides Combinatorial Coin Slides
Lesson 3: Modeling Distributions and Constraints
The Change-Maker's Dilemma
How many ways can you make $1.00 using pennies, nickels, and dimes?
Without GFs: Case-by-case analysis (slow, error-prone).
With GFs: Find the coefficient of \( x^{100} \) in a product of series.
The Mapping
Exponent Units (e.g., cents, items)
Coefficient Number of ways
The Power of \( \frac{1}{1-x^k} \)
Infinite Supply of Item (Value k)
\( 1 + x^k + x^{2k} + x^{3k} + \dots = \frac{1}{1-x^k} \)
This series represents choosing 0, 1, 2, ... items of weight \( k \).
Constraint Modeling
Constraint Series Term Exactly 1 \( x \) At most 3 \( (1+x+x^2+x^3) \) Even amount \( (1+x^2+x^4+\dots) \)
Balls in Bins
Distributing \( n \) identical balls into \( k \) distinct bins:
\( (1+x+x^2+\dots)^k = \frac{1}{(1-x)^k} \)
Generalized Binomial
\( \frac{1}{(1-x)^k} = \sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n \)
The coefficient of \( x^n \) is the famous Stars and Bars formula!
Summary: The Counting Rule
To solve a counting problem with independent choices:
Multiply the series for each choice.
The total ways to get sum \( S \) is the coefficient of \( x^S \).
\( [x^S] \prod_{i=1}^k \text{ChoiceSeries}_i(x) \)
Change Maker Activity Change Maker Activity
Modeling Constraints with Generating Functions
IDENTIFICATION
1 Simple Partitions
Write the generating function for the number of ways to partition an integer \( n \) into parts of size 1, 2, and 3 only (using any number of each).
Part Size 1
\( \frac{1}{1-x} \)
Part Size 2
Your Turn...
Part Size 3
Your Turn...
Final Product GF:
2 Fruit Basket Dilemma
How many ways can we select \( n \) pieces of fruit given these rules?
Apples: Must be an even number.Bananas: Must be a multiple of 5.Oranges: At most 4.Pears: Exactly 0 or 1.
Apples GF:
Bananas GF:
Oranges GF:
Pears GF:
3 The General Case
Find the number of ways to distribute 20 identical cookies among 3 graduate students so that each student gets at least 2 cookies .
Mathematical Workspace
Final Answer (Numerical):
Counting Constraints Teacher Guide Counting Constraints Teacher Guide
Lesson 3: Combinatorial Applications of Geometric Series
Core Concepts
In this lesson, we shift from sequence-solving to counting . The core insight is that the product of power series mirrors the additive nature of combinatorial choices.
Pedagogical Tip
Encourage students to read the GF aloud as a sentence: "One plus one apple plus two apples..." This bridges the gap between the symbolic algebra and the physical items.
Discussion Prompts
"Why does 'at most 4' result in a finite polynomial?"
"What happens to the GF if we require at least one of every item?"
"How does this relate to the 'Stars and Bars' method from undergraduate combinatorics?"
Answer Key
1. Simple Partitions
The generating function is the product of the three independent series:
\( A(x) = \frac{1}{(1-x)(1-x^2)(1-x^3)} \)
2. Fruit Basket Dilemma
Apples: \( 1+x^2+x^4+\dots = \frac{1}{1-x^2} \)Bananas: \( 1+x^5+x^{10}+\dots = \frac{1}{1-x^5} \)Oranges: \( 1+x+x^2+x^3+x^4 = \frac{1-x^5}{1-x} \)Pears: \( 1+x \)
The Simplified Product:
\( A(x) = \frac{1}{1-x^2} \cdot \frac{1}{1-x^5} \cdot \frac{1-x^5}{1-x} \cdot (1+x) = \frac{1+x}{(1-x^2)(1-x)} = \frac{1+x}{(1-x)(1+x)(1-x)} = \frac{1}{(1-x)^2} \)
Observation: Surprisingly, this basket is equivalent to having two bins for identical items!
3. The Cookies Problem
Each student gets \( (x^2 + x^3 + x^4 + \dots) = x^2(1+x+x^2+\dots) = \frac{x^2}{1-x} \).
Total GF: \( \left( \frac{x^2}{1-x} \right)^3 = \frac{x^6}{(1-x)^3} \).
We want the coefficient of \( x^{20} \) in \( x^6(1-x)^{-3} \), which is the coefficient of \( x^{14} \) in \( (1-x)^{-3} \).
Formula: \( [x^n] (1-x)^{-k} = \binom{n+k-1}{k-1} \)
Result: \( \binom{14+3-1}{3-1} = \binom{16}{2} = \frac{16 \cdot 15}{2} = 120 \).
Labeled Structures Slides Labeled Structure EGFs
Lesson 4: Permutations, Labels, and Exponential Series
Does Order Matter?
Ordinary Generating Functions (OGFs) excel at unlabeled structures (e.g., identical coins).
Unlabeled:
Sets of items where only quantity counts.
Exponential Generating Functions (EGFs) are built for labeled structures (e.g., distinct people).
Labeled:
Sequences, permutations, and ordered arrangements.
The Exponential Transformation
\( \hat{A}(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!} \)
Exponential Generating Function
The Standard EGF
For the sequence \( a_n = 1 \), the EGF is:
Why the \( n! \)?
The denominator cancels the internal orderings of a labeled structure of size \( n \).
The Exponential Product
If \( \hat{C}(x) = \hat{A}(x)\hat{B}(x) \), then:
\( c_n = \sum_{k=0}^n \binom{n}{k} a_k b_{n-k} \)
This is exactly how many ways to pick a \( k \)-subset from \( n \) labels and build an \( A \)-structure on it and a \( B \)-structure on the rest.
EGF Vocabulary
Structure EGF Form Set of items \( e^x \) Permutations \( 1/(1-x) \) Cycles \( \ln(1/(1-x)) \) At least one item \( e^x - 1 \)
Permutation Power Worksheet Permutation Power Worksheet
Lesson 4: Exponential Generating Functions (EGFs)
ID:
REFERENCE: THE EXPONENTIAL FORMULA
If \( \mathcal{C} = \text{Set}(\mathcal{S}) \), then \( \hat{C}(x) = \exp(\hat{S}(x)) \). This relates sets of connected components to their generating functions.
1. Sequence of Labels
How many labeled sequences of length \( n \) can be formed using the symbols {A, B} if there must be an even number of A's ?
EGF for A's (Even):
\( \frac{e^x + e^{-x}}{2} = \cosh(x) \)
EGF for B's (Any):
\( e^x \)
Workspace (Find the product and extract \( [x^n/n!] \)):
2. Counting Surjections
How many surjections (onto functions) exist from a set of \( n \) labeled elements to a set of \( k \) labeled elements?
Hint: Each element in the target set must be mapped to at least once. The EGF for "at least one" is \( (e^x - 1) \).
3. Derangements via Exponential Formula
A permutation is a derangement if it has no cycles of length 1 (no fixed points).
Using the Cycle-EGF \( \hat{Z}(x) = \ln \frac{1}{1-x} \), find the EGF for derangements \( \hat{D}(x) \).
DERIVATION AREA
Verify your result:
"The EGF for derangements should be \( \frac{e^{-x}}{1-x} \)." Explain why this makes sense relative to all permutations \( \frac{1}{1-x} \).
EGF Expert Answer Key EGF Expert Answer Key
Lesson 4: Labeled Combinatorial Structures
Problem 1: Sequences with Even A's
Product: \( \hat{A}(x) = \frac{e^x + e^{-x}}{2} \cdot e^x = \frac{e^{2x} + 1}{2} \)
Expansion: \( \frac{1}{2} \left( \sum \frac{(2x)^n}{n!} + 1 \right) \)
Extract \( [x^n/n!] \):
For \( n=0 \): \( \frac{1}{2}(2^0 + 1) = 1 \).
For \( n>0 \): \( \frac{2^n}{2} = 2^{n-1} \).
Final Answer: \( 2^{n-1} \) for \( n \ge 1 \).
Problem 2: Counting Surjections
Total EGF: \( (e^x - 1)^k \)
Using binomial theorem: \( (e^x - 1)^k = \sum_{j=0}^k \binom{k}{j} e^{jx} (-1)^{k-j} \)
Extract \( [x^n/n!] \):
\( S(n,k) \cdot k! = \sum_{j=0}^k (-1)^{k-j} \binom{k}{j} j^n \)
Note: These are precisely the Stirling numbers of the second kind multiplied by \( k! \).
Problem 3: Derangements
All permutations have EGF \( \frac{1}{1-x} \).
A permutation is a set of cycles. Cycles of length 1 have EGF \( x \).
EGF for all cycles: \( \hat{Z}(x) = x + \frac{x^2}{2} + \frac{x^3}{3} + \dots = \ln \frac{1}{1-x} \).
EGF for cycles of length \( \ge 2 \): \( \hat{Z}_{der}(x) = \hat{Z}(x) - x \).
EGF for derangements: \( \exp(\hat{Z}_{der}(x)) = \exp(\ln \frac{1}{1-x} - x) \)
\( = \frac{1}{1-x} \cdot e^{-x} \)
Intuition: Total permutations multiplied by the probability of having zero fixed points (the \( e^{-1} \) limit).
Snake Oil Slides Snake Oil Slides
Lesson 5: Evaluating Complex Combinatorial Sums
Is it Magic or Algebra?
Can we verify complex identities without doing arithmetic?
\( \sum_{k} \binom{n}{k} \binom{k}{m} = \binom{n}{m} 2^{n-m} \)
"The 'Snake Oil' method is so named because it seems to cure every summation problem."
— Herbert Wilf
The 4-Step Panacea
1. Identify the Target
Call your sum \( S_n \). Define \( f(x) = \sum S_n x^n \).
2. Swap the Sums
\( \sum_n \left( \sum_k \dots \right) x^n = \sum_k \left( \sum_n \dots x^n \right) \)
3. Evaluate the Inner Sum
The inner sum (over \( n \)) is usually a standard GF.
4. Extract Coefficients
Find \( [x^n] \) in the resulting simplified function.
Applying the Snake Oil
Evaluate \( \sum_k \binom{n}{k} \binom{k}{m} \):
\( \sum_n x^n \sum_k \binom{n}{k} \binom{k}{m} \dots \)
Swap: \( \sum_k \binom{k}{m} \sum_n \binom{n}{k} x^n \dots \)
Inner sum is \( \frac{x^k}{(1-x)^{k+1}} \)
Resulting sum: \( \sum_k \binom{k}{m} \frac{x^k}{(1-x)^{k+1}} = \frac{x^m}{(1-x)^{m+1}(1-\frac{x}{1-x})^{m+1}} \)
Final: \( \frac{x^m}{(1-2x)^{m+1}} \)
The Diagnosis
Use Snake Oil when:
Sum is over a variable \( k \) in a binomial.
The free variable \( n \) appears "cleanly".
Standard identities fail to simplify.
Final Mastery
Generating Functions turn thinking into calculating .
Identity Investigator Worksheet Identity Investigator Worksheet
Lesson 5 Mastery
1. The Classic Identity
Verify the identity \( \sum_{k=0}^n \binom{n}{k} = 2^n \) using the Snake Oil Method.
Yes, it's trivial, but follow the steps: Sum over n, swap, evaluate inner, extract.
2. Power of Squares
Evaluate the sum \( S_n = \sum_{k} \binom{n}{k} \binom{2k}{k} \left(-\frac{1}{4}\right)^k \).
Hint: The OGF for central binomial coefficients is \( \sum \binom{2k}{k} z^k = \frac{1}{\sqrt{1-4z}} \).
3. The Vandermonde Generalization
"True mastery is knowing when to sum over the dummy variable."
Prove that \( \sum_{k} \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n} \) using generating functions. Show that this is simply the coefficient extraction from the product of two binomial GFs.
Summary reflection:
Why is the term 'Snake Oil' appropriate for this algebraic technique?
Mastering Sums Teacher Guide Mastering Sums Teacher Guide
Lesson 5: The Snake Oil Method Answer Key
Teacher's Note
The "Snake Oil" method is a climax for the course. It demonstrates the ultimate utility of formal power series: they turn hard combinatorial problems into "mindless" algebraic manipulations. Graduate students should appreciate the shift from creative problem-solving to algorithmic verification.
1. Warm-up (Sum of Binomials)
Step 1: \( f(x) = \sum_n x^n \sum_k \binom{n}{k} \)
Step 2: \( f(x) = \sum_k \sum_n \binom{n}{k} x^n \)
Step 3: \( \sum_n \binom{n}{k} x^n = \frac{x^k}{(1-x)^{k+1}} \)
Step 4: \( f(x) = \sum_k \frac{x^k}{(1-x)^{k+1}} = \frac{1}{1-x} \sum_k \left(\frac{x}{1-x}\right)^k \)
Step 5: \( f(x) = \frac{1}{1-x} \cdot \frac{1}{1 - \frac{x}{1-x}} = \frac{1}{1-x} \cdot \frac{1-x}{1-2x} = \frac{1}{1-2x} \)
Result: \( [x^n] \frac{1}{1-2x} = 2^n \).
2. Power of Squares (Central Binomial)
Identity: \( S_n = \sum_k \binom{n}{k} \binom{2k}{k} (-1/4)^k \)
Swap sums: \( \sum_k \binom{2k}{k} (-1/4)^k \sum_n \binom{n}{k} x^n \)
Substitute inner: \( \sum_k \binom{2k}{k} (-1/4)^k \frac{x^k}{(1-x)^{k+1}} \)
Rearrange: \( \frac{1}{1-x} \sum_k \binom{2k}{k} \left( \frac{-x}{4(1-x)} \right)^k \)
Use GF for central binomial with \( z = \frac{-x}{4(1-x)} \):
\( f(x) = \frac{1}{1-x} \cdot \frac{1}{\sqrt{1 - 4z}} = \frac{1}{1-x} \cdot \frac{1}{\sqrt{1 - 4(\frac{-x}{4(1-x)})}} \)
\( f(x) = \frac{1}{1-x} \cdot \frac{1}{\sqrt{1 + \frac{x}{1-x}}} = \frac{1}{1-x} \cdot \sqrt{1-x} = \frac{1}{\sqrt{1-x}} \)
Result: \( [x^n] (1-x)^{-1/2} = \binom{n-1/2}{n} = \frac{\binom{2n}{n}}{2^{2n}} \).
3. Vandermonde Generalization
This is the simplest use of the product rule:
\( \binom{r+s}{n} = [x^n] (1+x)^{r+s} = [x^n] (1+x)^r (1+x)^s \)
By the Cauchy Product: \( [x^n] A(x)B(x) = \sum_{k=0}^n a_k b_{n-k} \)
Substituting the binomial coefficients gives the identity immediately.
