Advanced Counting

Goal: Formulate a recurrence relation for the number of plane regions $R_n$ created by $n$ lines and find its closed-form solution.

Step-by-Step Derivation:

1. Base Case ($n=0$): With $0$ lines, the plane is undivided, yielding exactly $1$ region. $$R_0 = 1$$
2. Formulate the Recurrence ($n \geq 1$): When the $n$-th line is added:
   • Since it is not parallel to any of the $n-1$ existing lines, it must intersect all $n-1$ lines in exactly $n-1$ distinct points.
   • Since no three lines are concurrent, these $n-1$ intersection points are distinct.
   • These $n-1$ points divide the $n$-th line into $n$ segments (two infinite rays and $n-2$ finite intervals).
   • Each segment of the $n$-th line passes through a pre-existing region and divides it into two. This adds exactly $1$ new region per segment, producing $n$ new regions in total.
   $$\text{Recurrence Relation: } R_n = R_{n-1} + n \quad \text{for } n \geq 1$$
3. Solve by Iteration: We sum the recurrence relation from $1$ to $n$: $$R_n - R_0 = \sum_{k=1}^n (R_k - R_{k-1}) = \sum_{k=1}^n k = \frac{n(n+1)}{2}$$ Substitute the base case $R_0 = 1$: $$R_n = 1 + \frac{n(n+1)}{2} = \frac{n^2+n+2}{2}$$

Conclusion: The recurrence relation is $R_n = R_{n-1} + n$ for $n \geq 1$ with $R_0 = 1$, and its closed-form solution is $R_n = \frac{n^2+n+2}{2}$. ∎

Goal: Set up a recurrence relation for the number of binary strings $a_n$ of length $n$ containing at least one pair of consecutive zeros.

Step-by-Step Derivation:

1. Analyze cases based on ending bits: Let $a_n$ be the number of valid strings of length $n$. We partition the set of valid strings by their ending patterns:
   • Case 1 (Ends in 1): The string is of the form $S_{n-1}1$. The consecutive zeros must occur in the prefix $S_{n-1}$. There are $a_{n-1}$ such strings.
   • Case 2 (Ends in 10): The string is of the form $S_{n-2}10$. The consecutive zeros must occur in the prefix $S_{n-2}$. There are $a_{n-2}$ such strings.
   • Case 3 (Ends in 00): The string is of the form $S_{n-2}00$. Regardless of the prefix $S_{n-2}$, this string always contains consecutive zeros (at the end). The prefix $S_{n-2}$ can be any binary string of length $n-2$. There are $2^{n-2}$ such strings.
   Since these cases are mutually exclusive and cover all valid endings, we sum their counts: $$a_n = a_{n-1} + a_{n-2} + 2^{n-2} \quad \text{for } n \geq 3$$
2. Determine Initial Conditions:
   • $n=1$: Strings are $\{0, 1\}$. None contain consecutive zeros $\implies a_1 = 0$.
   • $n=2$: Strings are $\{00, 01, 10, 11\}$. Only $00$ is valid $\implies a_2 = 1$.

Conclusion: The recurrence relation is $a_n = a_{n-1} + a_{n-2} + 2^{n-2}$ for $n \geq 3$, with initial conditions $a_1 = 0$ and $a_2 = 1$. ∎

Goal: Formulate a recurrence relation for the salary $S_n$ in year $n$.

Step-by-Step Derivation:

1. Identify the base case: The starting salary in the first year ($n=1$) is given directly: $$S_1 = 50{,}000$$
2. Formulate the recurrence: For any year $n > 1$, the salary $S_n$ is equal to:
   • Double the salary of the previous year: $2S_{n-1}$
   • Plus an additional bonus of $\$10{,}000 \cdot n$ for the $n$-th year.
   Combining these terms yields: $$S_n = 2 S_{n-1} + 10{,}000n \quad \text{for } n \geq 2$$

Conclusion: The recurrence relation is $S_n = 2 S_{n-1} + 10{,}000n$ for $n \geq 2$, with initial condition $S_1 = 50{,}000$. ∎

Goal: Formally verify that $a_n = -2^{n+1}$ satisfies the recurrence relation $a_n = 3a_{n-1} + 2^n$.

Proof:

1. Substitute the candidate formula into the RHS: If $a_n = -2^{n+1}$, then the term for $n-1$ is: $$a_{n-1} = -2^{(n-1)+1} = -2^n$$ Substitute $a_{n-1}$ into the right-hand side of the recurrence: $$\text{RHS} = 3 a_{n-1} + 2^n = 3(-2^n) + 2^n$$
2. Simplify the algebraic expression: Factor out $2^n$ from the terms: $$\text{RHS} = (-3 + 1) \cdot 2^n = -2 \cdot 2^n = -2^{n+1}$$
3. Compare with the LHS: The left-hand side of the recurrence is: $$\text{LHS} = a_n = -2^{n+1}$$ Since $\text{LHS} = \text{RHS} = -2^{n+1}$ for all $n \geq 1$, the candidate function is a valid solution. ∎

Goal: Find the explicit closed-form solutions for each of the four recurrence relations.

Step-by-Step Solutions:

• (a) $a_n = 2a_{n-1}$, $a_0 = 3$: This is a first-order linear homogeneous recurrence. By induction: $$a_n = a_0 \cdot 2^n = 3 \cdot 2^n \quad \text{for } n \geq 0$$
• (b) $a_n = a_{n-1}$, $a_0 = 2$: This represents a constant sequence where each term equals the previous. $$a_n = a_0 = 2 \quad \text{for } n \geq 0$$
• (c) $a_n = 4a_{n-2}$, $a_0 = 0, a_1 = 4$: Write the characteristic equation: $r^2 - 4 = 0 \implies r = \pm 2$. The general solution is: $$a_n = \alpha \cdot 2^n + \beta \cdot (-2)^n$$ Substitute the initial conditions:
  • $a_0 = \alpha + \beta = 0 \implies \beta = -\alpha$
  • $a_1 = 2\alpha - 2\beta = 4 \implies 2\alpha - 2(-\alpha) = 4 \implies 4\alpha = 4 \implies \alpha = 1, \beta = -1$
  $$a_n = 2^n - (-2)^n \quad \text{for } n \geq 0$$
• (d) $a_n = a_{n-2}/4$, $a_0 = 1, a_1 = 0$: The characteristic equation is $r^2 - 1/4 = 0 \implies r = \pm 1/2$. The general solution is: $$a_n = \alpha \cdot \left(\frac{1}{2}\right)^n + \beta \cdot \left(-\frac{1}{2}\right)^n$$ Apply the initial conditions:
  • $a_0 = \alpha + \beta = 1$
  • $a_1 = \frac{1}{2}\alpha - \frac{1}{2}\beta = 0 \implies \alpha = \beta$
  Since $\alpha = \beta$, we have $2\alpha = 1 \implies \alpha = \beta = \frac{1}{2}$. $$a_n = \frac{1}{2}\left(\left(\frac{1}{2}\right)^n + \left(-\frac{1}{2}\right)^n\right) = \left(\frac{1}{2}\right)^{n+1} + (-1)^n \left(\frac{1}{2}\right)^{n+1} \quad \text{for } n \geq 0$$

∎

Goal: Classify each recurrence relation as a Linear Homogeneous Recurrence with Constant Coefficients (LHRCC), and state the degree if it is one, or specify the failing condition.

Classification Analysis:

1. (a) $a_n = 3a_{n-1} + 4a_{n-2} + 5a_{n-3}$: Linear in all terms, homogeneous (no standalone $n$-dependent or constant term), and coefficients ($3, 4, 5$) are constant. The degree is $n - (n-3) = 3$. Status: LHRCC, Degree 3.
2. (b) $a_n = 2na_{n-1} + a_{n-2}$: The coefficient $2n$ of the $a_{n-1}$ term varies with $n$. Status: Not LHRCC (variable coefficients).
3. (c) $a_n = a_{n-1} + a_{n-4}$: Linear, homogeneous, constant coefficients. The degree is $n - (n-4) = 4$. Status: LHRCC, Degree 4.
4. (d) $a_n = a_{n-1} + 2$: The constant term $+2$ is non-zero. Status: Not LHRCC (non-homogeneous).
5. (e) $a_n = a_{n-1}^2 + a_{n-2}$: The term $a_{n-1}^2$ is non-linear. Status: Not LHRCC (non-linear).
6. (f) $a_n = a_{n-2}$: Linear, homogeneous, constant coefficients. The degree is $n - (n-2) = 2$. Status: LHRCC, Degree 2.
7. (g) $a_n = a_{n-1} + n$: The term $+n$ is a non-zero function of $n$. Status: Not LHRCC (non-homogeneous).

∎

Goal: Solve the second-order LHRCC recurrence $a_n - 5a_{n-1} + 6a_{n-2} = 0$ using the characteristic equation method.

Step-by-Step Solution:

1. Find the characteristic equation: Assume a solution of the form $a_n = r^n$. Substituting this yields the characteristic polynomial: $$r^2 - 5r + 6 = 0$$
2. Find the roots: Factor the quadratic equation: $$(r-2)(r-3) = 0 \implies r_1 = 2, r_2 = 3$$
3. Formulate the general solution: Since the roots are distinct, the general solution is a linear combination: $$a_n = \alpha \cdot 2^n + \beta \cdot 3^n$$
4. Apply initial conditions: Substitute $n=0$ and $n=1$: $$\begin{cases} a_0 = \alpha + \beta = 1 \\ a_1 = 2\alpha + 3\beta = 0 \end{cases}$$
5. Solve the system of equations: From the first equation, $\beta = 1 - \alpha$. Substitute into the second equation: $$2\alpha + 3(1 - \alpha) = 0 \implies -\alpha + 3 = 0 \implies \alpha = 3$$ $$\beta = 1 - 3 = -2$$

Conclusion: Substituting the coefficients back gives the explicit solution: $$a_n = 3\cdot 2^n - 2\cdot 3^n \quad \text{for } n \geq 0$$ ∎

Goal: Solve the second-order LHRCC recurrence with repeated roots.

Step-by-Step Solution:

1. Find the characteristic equation: $$r^2 - 4r + 4 = 0$$
2. Find the roots: $$(r-2)^2 = 0 \implies r = 2 \quad \text{(multiplicity 2)}$$
3. Formulate the general solution: For a repeated root $r=2$, the general solution includes a linear factor in $n$: $$a_n = (\alpha + \beta n) \cdot 2^n$$
4. Apply initial conditions: Substitute $n=0$ and $n=1$:
   • $a_0 = (\alpha + 0) \cdot 2^0 = \alpha = 6$
   • $a_1 = (\alpha + \beta) \cdot 2^1 = 2(6 + \beta) = 8 \implies 6 + \beta = 4 \implies \beta = -2$
5. Construct final equation: $$a_n = (6 - 2n)2^n = (3 - n)2^{n+1}$$

Conclusion: The explicit solution is $a_n = (3 - n)2^{n+1}$ for $n \geq 0$. ∎

Goal: Solve the third-order LHRCC recurrence $a_n + 3a_{n-1} + 3a_{n-2} + a_{n-3} = 0$ using characteristic equation methods.

Step-by-Step Solution:

1. Find the characteristic equation: $$r^3 + 3r^2 + 3r + 1 = 0$$
2. Find the roots: Recognize this as a perfect binomial cube: $$(r+1)^3 = 0 \implies r = -1 \quad \text{(multiplicity 3)}$$
3. Formulate the general solution: Since $r=-1$ has multiplicity 3, the general solution is: $$a_n = (\alpha + \beta n + \gamma n^2) \cdot (-1)^n$$
4. Apply initial conditions: Substitute $n=0, 1, 2$:
   • $n=0 \implies a_0 = \alpha \cdot 1 = 5 \implies \alpha = 5$
   • $n=1 \implies a_1 = (5 + \beta + \gamma) \cdot (-1) = -9 \implies 5 + \beta + \gamma = 9 \implies \beta + \gamma = 4$
   • $n=2 \implies a_2 = (5 + 2\beta + 4\gamma) \cdot 1 = 15 \implies 2\beta + 4\gamma = 10 \implies \beta + 2\gamma = 5$
5. Solve for $\beta$ and $\gamma$: Subtract the equation $\beta + \gamma = 4$ from $\beta + 2\gamma = 5$: $$(\beta + 2\gamma) - (\beta + \gamma) = 5 - 4 \implies \gamma = 1$$ Substituting $\gamma = 1$ back into $\beta + \gamma = 4$: $$\beta + 1 = 4 \implies \beta = 3$$

Conclusion: Substituting the coefficients yields the explicit solution: $$a_n = (5 + 3n + n^2)(-1)^n \quad \text{for } n \geq 0$$ ∎

Goal: Solve the first-order non-homogeneous recurrence relation $a_n - 2a_{n-1} = 3^n$.

Step-by-Step Solution:

1. Find the homogeneous solution $a_n^{(h)}$: The homogeneous recurrence is $a_n - 2a_{n-1} = 0$, which has the characteristic equation $r - 2 = 0 \implies r = 2$. $$a_n^{(h)} = \alpha \cdot 2^n$$
2. Find the particular solution $a_n^{(p)}$: The non-homogeneous term is $F(n) = 3^n$. Since the base $3$ is not a root of the homogeneous equation ($r = 2$), we guess a particular solution of the form: $$a_n^{(p)} = C \cdot 3^n$$ Substitute $a_n^{(p)}$ into the recurrence: $$C \cdot 3^n = 2(C \cdot 3^{n-1}) + 3^n$$ Divide both sides by $3^{n-1}$: $$3C = 2C + 3 \implies C = 3$$ So, the particular solution is: $$a_n^{(p)} = 3 \cdot 3^n = 3^{n+1}$$
3. Formulate the general solution: $$a_n = a_n^{(h)} + a_n^{(p)} = \alpha \cdot 2^n + 3^{n+1}$$
4. Apply the initial condition $a_1 = 5$: $$a_1 = \alpha \cdot 2^1 + 3^{1+1} = 5 \implies 2\alpha + 9 = 5 \implies 2\alpha = -4 \implies \alpha = -2$$

Conclusion: The general solution is $a_n = \alpha \cdot 2^n + 3^{n+1}$, and the specific solution with $a_1=5$ is: $$a_n = 3^{n+1} - 2^{n+1} \quad \text{for } n \geq 1$$ ∎

Goal: Find the general solution of the second-order non-homogeneous recurrence relation with mixed exponential and polynomial terms.

Step-by-Step Solution:

1. Solve the homogeneous part: The homogeneous recurrence is $a_n - 5a_{n-1} + 6a_{n-2} = 0$, which has the characteristic equation: $$r^2 - 5r + 6 = 0 \implies (r-2)(r-3) = 0 \implies r_1 = 2, r_2 = 3$$ $$a_n^{(h)} = A \cdot 2^n + B \cdot 3^n$$
2. Find the particular solution for the $2^n$ term: Because the base $2$ is a characteristic root of multiplicity 1, our guess must be multiplied by $n$: $$a_n^{(p1)} = q n 2^n$$ Substitute $a_n^{(p1)}$ into the recurrence $a_n - 5a_{n-1} + 6a_{n-2} = 2^n$: $$qn 2^n - 5q(n-1)2^{n-1} + 6q(n-2)2^{n-2} = 2^n$$ Divide by $2^{n-2}$: $$4qn - 10q(n-1) + 6q(n-2) = 4 \implies 4qn - 10qn + 10q + 6qn - 12q = 4$$ $$-2q = 4 \implies q = -2$$ Thus, $a_n^{(p1)} = -2n 2^n = -n 2^{n+1}$.
3. Find the particular solution for the $3n$ term: Since $3n$ is a linear polynomial and $1$ is not a characteristic root, we guess: $$a_n^{(p2)} = p_1 n + p_2$$ Substitute $a_n^{(p2)}$ into the recurrence $a_n - 5a_{n-1} + 6a_{n-2} = 3n$: $$(p_1 n + p_2) - 5(p_1(n-1) + p_2) + 6(p_1(n-2) + p_2) = 3n$$ $$2p_1 n + (2p_2 - 7p_1) = 3n$$ Equating coefficients of identical powers of $n$:
   • $2p_1 = 3 \implies p_1 = \frac{3}{2}$
   • $2p_2 - 7p_1 = 0 \implies 2p_2 = 7 \cdot \frac{3}{2} = \frac{21}{2} \implies p_2 = \frac{21}{4}$
   Thus, $a_n^{(p2)} = \frac{3}{2}n + \frac{21}{4}$.
4. Assemble the general solution: $$a_n = a_n^{(h)} + a_n^{(p1)} + a_n^{(p2)} = A \cdot 2^n + B \cdot 3^n - n \cdot 2^{n+1} + \frac{3}{2}n + \frac{21}{4}$$

∎

Goal: Find the asymptotic bounds of the divide-and-conquer recurrence relation using the Master Theorem.

Step-by-Step Analysis:

1. Identify the parameters of the recurrence: $$T(n) = a T(n/b) + f(n)$$ Here, $a = 5$, $b = 2$, and $f(n) = 3 = \Theta(1) = \Theta(n^0)$.
2. Compute the critical log boundary value: $$c^* = \log_b a = \log_2 5 \approx 2.32$$
3. Compare $f(n)$ to $n^{c^*}$: We compare $f(n) = \Theta(n^0)$ with $n^{\log_2 5}$. Since $0 < \log_2 5$, we have $f(n) = O(n^{\log_2 5 - \epsilon})$ for any $0 < \epsilon \leq 2.32$. This satisfies Case 1 of the Master Theorem.
4. Apply Case 1: $$T(n) = \Theta(n^{\log_b a}) = \Theta(n^{\log_2 5})$$

Conclusion: By Case 1 of the Master Theorem, $f(n) = \Theta(n^{\log_2 5})$. ∎

Goal: Determine the asymptotic complexity of the recurrence $f(n) = 2f(n/3) + 4$.

Step-by-Step Analysis:

1. Identify parameters: $a = 2$, $b = 3$, and $f(n) = 4 = \Theta(n^0)$.
2. Compute critical exponent: $$c^* = \log_b a = \log_3 2 \approx 0.63$$
3. Compare: Compare $n^0$ with $n^{\log_3 2}$. Since $0 < \log_3 2$, we have $f(n) = O(n^{\log_3 2 - \epsilon})$ for any $0 < \epsilon \leq 0.63$. This corresponds to Case 1 of the Master Theorem.
4. State complexity: $$f(n) = \Theta(n^{\log_3 2})$$

Conclusion: The asymptotic complexity is $f(n) = \Theta(n^{\log_3 2})$. ∎

Goal: Find the asymptotic behavior of the recurrence $f(n) = 8f(n/2) + n^2$.

Step-by-Step Analysis:

1. Identify parameters: $a = 8$, $b = 2$, and $f(n) = n^2 = \Theta(n^2)$.
2. Compute critical exponent: $$c^* = \log_b a = \log_2 8 = 3$$
3. Compare: We compare $f(n) = \Theta(n^2)$ with $n^3$. Since $2 < 3$, we have $f(n) = O(n^{3 - \epsilon})$ for $\epsilon = 1 > 0$. This matches Case 1 of the Master Theorem.
4. Apply Case 1: $$f(n) = \Theta(n^{\log_b a}) = \Theta(n^3)$$

Conclusion: The asymptotic complexity is $f(n) = \Theta(n^3)$. ∎

Goal: Find the exact value of $f(16)$ and the asymptotic complexity of the non-standard recurrence $f(n) = 2f(\sqrt{n}) + 1$.

Step-by-Step Analysis:

1. Substitute variables: Let $n = 2^k \implies k = \log_2 n$. Define a new function $g(k) = f(2^k)$. Since $\sqrt{n} = (2^k)^{1/2} = 2^{k/2}$, the recurrence relation becomes: $$g(k) = 2g(k/2) + 1$$ The base case $f(2) = 1$ translates to $g(1) = 1$ (since $2 = 2^1$).
2. Solve for $g(k)$ using the Master Theorem: For the recurrence $g(k) = 2g(k/2) + 1$:
   • $a = 2$, $b = 2$, $c^* = \log_2 2 = 1$.
   • Since the non-recursive term $1 = \Theta(k^0)$ has $0 < 1$, this is Case 1 of the Master Theorem.
   • Thus, $g(k) = \Theta(k^1) = \Theta(k)$.
3. Substitute back to find $f(n)$: Since $k = \log_2 n$, we have: $$f(n) = g(\log_2 n) = \Theta(\log n)$$
4. Compute $f(16)$ exactly: For $n = 16 = 2^4$, we have $k = 4$. We compute $g(4)$ iteratively:
   • $g(1) = 1$
   • $g(2) = 2g(1) + 1 = 2(1) + 1 = 3$
   • $g(4) = 2g(2) + 1 = 2(3) + 1 = 7$
   Therefore, $f(16) = g(4) = 7$.

Conclusion: The asymptotic bound is $f(n) = \Theta(\log n)$, and the exact value is $f(16) = 7$. ∎

Goal: Determine the correct asymptotic growth class for the given recurrence and initial conditions.

Step-by-Step Derivation:

1. Solve the recurrence relation: The characteristic equation is: $$r^2 - 5r + 6 = 0 \implies (r-2)(r-3) = 0 \implies r_1 = 2, r_2 = 3$$ The general solution is: $$T(n) = A \cdot 2^n + B \cdot 3^n$$
2. Find parameters $A$ and $B$: Substitute $n=0$ and $n=1$: $$\begin{cases} T(0) = A + B = 1 \implies A = 1 - B \\ T(1) = 2A + 3B = 2 \end{cases}$$ Substitute $A$ into the second equation: $$2(1 - B) + 3B = 2 \implies 2 + B = 2 \implies B = 0$$ $$A = 1 - 0 = 1$$
3. Write specific solution: $$T(n) = 1 \cdot 2^n + 0 \cdot 3^n = 2^n$$ Thus, $T(n) = \Theta(2^n)$.

Conclusion: The correct option is (A) since $T(n) = 2^n = \Theta(2^n)$. ∎

Goal: Find the asymptotic order of the recurrence relation $T(n) = T(n-1) + 2(n-1)$ for $n \geq 2$.

Step-by-Step Derivation:

1. Expand the recurrence relation: $$T(n) = T(n-1) + 2(n-1)$$ $$T(n) = [T(n-2) + 2(n-2)] + 2(n-1)$$ Continuing this back-substitution down to $T(1)$: $$T(n) = T(1) + \sum_{k=1}^{n-1} 2k$$
2. Sum the series: Substitute $T(1) = 10$: $$T(n) = 10 + 2 \sum_{k=1}^{n-1} k = 10 + 2 \cdot \frac{(n-1)n}{2} = 10 + n(n-1) = n^2 - n + 10$$
3. Determine asymptotic growth: The highest power of $n$ is $n^2$. Thus, $T(n) = \Theta(n^2)$.

Conclusion: The asymptotic order of the recurrence is $\Theta(n^2)$. ∎

Goal: Express the generating function $\sum_{k=0}^\infty a_k x^k$ in a closed algebraic form for each sequence.

Step-by-Step Derivation:

• (a) $0,2,2,2,2,2,0,0,\dots$: The non-zero terms are $a_1 = a_2 = a_3 = a_4 = a_5 = 2$. $$F(x) = 2x + 2x^2 + 2x^3 + 2x^4 + 2x^5 = 2x(1 + x + x^2 + x^3 + x^4) = \frac{2x(1-x^5)}{1-x}$$
• (b) $0,0,0,1,1,1,\dots$: Here $a_k = 1$ for all $k \geq 3$. $$F(x) = x^3 + x^4 + x^5 + \dots = x^3(1 + x + x^2 + \dots) = \frac{x^3}{1-x}$$
• (c) $0,1,0,0,1,0,0,1,\dots$: The non-zero terms are $a_k = 1$ at indices $k = 1, 4, 7, 10, \dots$. $$F(x) = x + x^4 + x^7 + x^{10} + \dots = x(1 + x^3 + x^6 + \dots) = \frac{x}{1-x^3}$$
• (d) $2,4,8,16,\dots$: Here $a_k = 2^{k+1}$ for all $k \geq 0$. $$F(x) = 2 + 4x + 8x^2 + 16x^3 + \dots = 2(1 + 2x + 4x^2 + 8x^3 + \dots) = \frac{2}{1-2x}$$
• (e) $\binom{7}{0}, \binom{7}{1}, \dots, \binom{7}{7}, 0, 0, \dots$: Using the binomial theorem: $$F(x) = \sum_{k=0}^7 \binom{7}{k} x^k = (1+x)^7$$
• (f) $2,-2,2,-2,\dots$: Here $a_k = 2 \cdot (-1)^k$ for all $k \geq 0$. $$F(x) = 2 - 2x + 2x^2 - 2x^3 + \dots = 2(1 - x + x^2 - x^3 + \dots) = \frac{2}{1+x}$$
• (g) $1,1,0,1,1,1,\dots$: This is the constant sequence of 1s except at $a_2 = 0$. $$F(x) = \left(\sum_{k=0}^\infty x^k\right) - x^2 = \frac{1}{1-x} - x^2$$
• (h) $0,0,0,1,2,3,\dots$: The sequence is $a_3=1, a_4=2, a_5=3, \dots$, which corresponds to $a_k = k-2$ for $k \geq 3$. $$F(x) = 1x^3 + 2x^4 + 3x^5 + \dots = x^2(1x^1 + 2x^2 + 3x^3 + \dots) = x^2 \sum_{j=1}^\infty j x^j$$ Recall that $\sum_{j=1}^\infty j x^j = \frac{x}{(1-x)^2}$. Substituting this gives: $$F(x) = x^2 \cdot \frac{x}{(1-x)^2} = \frac{x^3}{(1-x)^2}$$

∎

Goal: Determine the explicit coefficient formula $a_k$ for the power series expansion of each generating function.

Step-by-Step Derivation:

• (a) $A(x) = (3x-4)^3$: Expand using the binomial theorem: $$(3x-4)^3 = \sum_{k=0}^3 \binom{3}{k} (3x)^k (-4)^{3-k} = \sum_{k=0}^3 \left[\binom{3}{k} 3^k (-4)^{3-k}\right] x^k$$ So, $a_k = \binom{3}{k} 3^k (-4)^{3-k}$ for $0 \leq k \leq 3$, and $a_k = 0$ for $k \geq 4$.
• (b) $B(x) = \frac{1}{1-5x}$: This is a geometric series with ratio $5x$: $$\frac{1}{1-5x} = \sum_{k=0}^\infty (5x)^k = \sum_{k=0}^\infty 5^k x^k \implies a_k = 5^k \quad \text{for } k \geq 0$$
• (c) $C(x) = \frac{x^3}{1+3x}$: Expand the geometric series part: $$\frac{1}{1 - (-3x)} = \sum_{j=0}^\infty (-3)^j x^j$$ Multiply by $x^3$: $$C(x) = x^3 \sum_{j=0}^\infty (-3)^j x^j = \sum_{j=0}^\infty (-3)^j x^{j+3}$$ Substitute $k = j+3 \implies j = k-3$. The series starts at $k=3$. $$a_k = (-3)^{k-3} \quad \text{for } k \geq 3, \text{ and } a_k = 0 \text{ for } k < 3$$
• (d) $D(x) = \frac{x^2}{(1-x)^2}$: Recall the power series expansion: $$\frac{1}{(1-x)^2} = \sum_{j=0}^\infty (j+1)x^j$$ Multiply by $x^2$: $$D(x) = x^2 \sum_{j=0}^\infty (j+1)x^j = \sum_{j=0}^\infty (j+1)x^{j+2}$$ Let $k = j+2 \implies j+1 = k-1$. The series starts at $k=2$. $$a_k = k-1 \quad \text{for } k \geq 2, \text{ and } a_k = 0 \text{ for } k < 2$$
• (e) $E(x) = 2e^{2x}$: Expand using the definition of the exponential function: $$2e^{2x} = 2 \sum_{k=0}^\infty \frac{(2x)^k}{k!} = \sum_{k=0}^\infty \left[\frac{2^{k+1}}{k!}\right] x^k \implies a_k = \frac{2^{k+1}}{k!} \quad \text{for } k \geq 0$$

∎

Goal: Find the number of ways to distribute 8 identical cookies to 3 children with the constraint that each child receives $c_i \in \{2, 3, 4\}$ cookies.

Step-by-Step Derivation:

1. Set up individual child generating function: Since each child must get between 2 and 4 cookies, the options for one child are represented by: $$f(x) = x^2 + x^3 + x^4$$
2. Set up total generating function: For 3 distinct children, the total distribution generating function is: $$F(x) = (f(x))^3 = (x^2 + x^3 + x^4)^3 = x^6(1 + x + x^2)^3$$
3. Identify the required coefficient: We need the number of ways to distribute exactly 8 cookies, which is the coefficient of $x^8$ in $F(x)$: $$[x^8] F(x) = [x^8] x^6(1 + x + x^2)^3 = [x^2] (1 + x + x^2)^3$$
4. Expand $(1+x+x^2)^3$: We can expand this trinomial directly using the multinomial theorem, looking for combinations of exponents $(e_1, e_2, e_3)$ from $\{0, 1, 2\}$ that sum to 2: $$(1+x+x^2)^3 = (1+x+x^2)(1+x+x^2)(1+x+x^2)$$ The combinations of powers that multiply to $x^2$ are:
   • $x^2 \cdot 1 \cdot 1$ (occurs in 3 distinct permutations: child 1, child 2, or child 3 gets 2, others get 0) $\implies 3$ ways
   • $x \cdot x \cdot 1$ (occurs in 3 distinct permutations: one child gets 0, the other two get 1) $\implies 3$ ways
   Summing these yields $3 + 3 = 6$.

Conclusion: The coefficient of $x^8$ is 6, meaning there are 6 ways to distribute the cookies. ∎

Goal: Calculate the number of ways to distribute 10 identical balloons to 4 children with the constraint that each child receives $b_i \geq 2$ balloons.

Step-by-Step Derivation:

1. Set up individual child generating function: $$f(x) = x^2 + x^3 + x^4 + \dots = x^2 (1 + x + x^2 + \dots) = \frac{x^2}{1-x}$$
2. Set up total generating function: For 4 distinct children: $$F(x) = (f(x))^4 = \left(\frac{x^2}{1-x}\right)^4 = \frac{x^8}{(1-x)^4}$$
3. Find the coefficient of $x^{10}$: We need the coefficient of $x^{10}$ in $F(x)$: $$[x^{10}] F(x) = [x^{10}] \frac{x^8}{(1-x)^4} = [x^2] (1-x)^{-4}$$
4. Expand $(1-x)^{-4}$ using negative binomial series: $$(1-x)^{-4} = \sum_{k=0}^\infty \binom{k+4-1}{k} x^k = \sum_{k=0}^\infty \binom{k+3}{3} x^k$$ For $k = 2$, the coefficient is: $$\binom{2+3}{3} = \binom{5}{3} = \frac{5 \cdot 4 \cdot 3}{3 \cdot 2 \cdot 1} = 10$$

Conclusion: There are 10 ways to distribute the balloons. ∎

Goal: Find the explicit closed-form formula for the recurrence relation using the generating function method.

Step-by-Step Derivation:

1. Define the generating function: Let $A(x) = \sum_{n=1}^\infty a_n x^n$ be the generating function (sum starts at $n=1$).
2. Apply the recurrence to the generating function: Multiply both sides of $a_n = 8a_{n-1} + 10^{n-1}$ by $x^n$ and sum from $n=2$ to $\infty$: $$\sum_{n=2}^\infty a_n x^n = 8 \sum_{n=2}^\infty a_{n-1} x^n + \sum_{n=2}^\infty 10^{n-1} x^n$$
3. Rewrite terms in terms of $A(x)$:
   • $\sum_{n=2}^\infty a_n x^n = A(x) - a_1 x = A(x) - 9x$
   • $8 \sum_{n=2}^\infty a_{n-1} x^n = 8x \sum_{n=2}^\infty a_{n-1} x^{n-1} = 8x A(x)$
   • $\sum_{n=2}^\infty 10^{n-1} x^n = x \sum_{n=2}^\infty (10x)^{n-1} = x \left(\frac{10x}{1-10x}\right) = \frac{10x^2}{1-10x}$
4. Solve for $A(x)$: $$A(x) - 9x = 8x A(x) + \frac{10x^2}{1-10x}$$ $$A(x)(1 - 8x) = 9x + \frac{10x^2}{1-10x} = \frac{9x(1-10x) + 10x^2}{1-10x} = \frac{9x - 80x^2}{1-10x}$$ $$A(x) = \frac{9x - 80x^2}{(1 - 8x)(1 - 10x)}$$
5. Perform partial fraction decomposition: To find the coefficients of the expansion of $A(x) = \frac{9x - 80x^2}{(1-8x)(1-10x)}$, we factor out $x$ and decompose the remaining rational function: $$\frac{A(x)}{x} = \frac{9 - 80x}{(1-8x)(1-10x)} = \frac{C_1}{1-8x} + \frac{C_2}{1-10x}$$ Multiplying by the denominator gives: $$9 - 80x = C_1(1-10x) + C_2(1-8x)$$ We solve for $C_1$ and $C_2$ using strategic substitution:
   • Let $x = 1/10 \implies 9 - 8 = C_2(1 - 8/10) \implies 1 = C_2(2/10) \implies C_2 = 5$
   • Let $x = 1/8 \implies 9 - 10 = C_1(1 - 10/8) \implies -1 = C_1(-2/8) \implies C_1 = 4$
   Substitute these back into $A(x) = x \left(\frac{C_1}{1-8x} + \frac{C_2}{1-10x}\right)$: $$A(x) = \frac{4x}{1-8x} + \frac{5x}{1-10x} = 4x \sum_{n=0}^\infty (8x)^n + 5x \sum_{n=0}^\infty (10x)^n$$ $$A(x) = \sum_{n=0}^\infty 4 \cdot 8^n x^{n+1} + \sum_{n=0}^\infty 5 \cdot 10^n x^{n+1}$$ Shift indices ($m = n+1 \implies n = m-1$): $$A(x) = \sum_{m=1}^\infty \left[ 4 \cdot 8^{m-1} + 5 \cdot 10^{m-1} \right] x^m$$ Rewrite coefficients: $$a_m = 4 \cdot 8^{m-1} + 5 \cdot 10^{m-1} = \frac{1}{2} \cdot 8^m + \frac{1}{2} \cdot 10^m = \frac{8^m + 10^m}{2}$$

Conclusion: The solution to the recurrence relation is $a_n = \frac{8^n + 10^n}{2}$ for $n \geq 1$. ∎

Goal: Find the closed-form generating function $G(x)$ for the sequence of binomial coefficients.

Step-by-Step Derivation:

1. Write the definition of the generating function: $$G(x) = \sum_{k=0}^\infty a_k x^k$$
2. Substitute the sequence values: Since $a_k = \binom{m}{k}$ for $k \leq m$ and $0$ for $k > m$, the infinite sum becomes a finite sum: $$G(x) = \sum_{k=0}^m \binom{m}{k} x^k$$
3. Apply the Binomial Theorem: Recall the expansion of $(a+b)^m$: $$(a+b)^m = \sum_{k=0}^m \binom{m}{k} a^{m-k} b^k$$ Setting $a = 1$ and $b = x$: $$(1+x)^m = \sum_{k=0}^m \binom{m}{k} (1)^{m-k} x^k = \sum_{k=0}^m \binom{m}{k} x^k$$

Conclusion: The generating function is $G(x) = (1+x)^m$. ∎

Goal: Formulate the generating functions for paying $\$r$ in tokens under ordered and unordered constraints.

Step-by-Step Analysis:

1. (a) Order does not matter: When the order of tokens is irrelevant, this is modeled as integer partitions with restricted part sizes $\{1, 2, 5\}$. Each token type can be selected any number of times:
   • $\$1$ tokens contribute: $1 + x + x^2 + \dots = \frac{1}{1-x}$
   • $\$2$ tokens contribute: $1 + x^2 + x^4 + \dots = \frac{1}{1-x^2}$
   • $\$5$ tokens contribute: $1 + x^5 + x^{10} + \dots = \frac{1}{1-x^5}$
   Multiply these independent GFs: $$F(x) = \frac{1}{(1-x)(1-x^2)(1-x^5)}$$ The coefficient of $x^r$ in $F(x)$ represents the number of ways.
2. (b) Order matters: When order matters, this represents an ordered composition. A single coin payment is represented by the generating function: $$T(x) = x^1 + x^2 + x^5$$ Using exactly $k$ coins corresponds to $(T(x))^k$. To find the total ways across any number of coins, we sum over all possible coin counts $k \geq 0$: $$H(x) = \sum_{k=0}^\infty (T(x))^k = \sum_{k=0}^\infty (x+x^2+x^5)^k$$ This is an infinite geometric series with ratio $x+x^2+x^5$. Evaluating it yields: $$H(x) = \frac{1}{1 - (x + x^2 + x^5)} = \frac{1}{1 - x - x^2 - x^5}$$ The coefficient of $x^r$ in $H(x)$ represents the number of ways.

Conclusion: (a) Unordered GF: $F(x) = \frac{1}{(1-x)(1-x^2)(1-x^5)}$. (b) Ordered GF: $H(x) = \frac{1}{1 - x - x^2 - x^5}$. ∎