18  Exercises

  1. Given that \(\displaystyle \frac{1}{1 - ax} = \sum_{n = 0}^\infty a^n x^n\), convert the following into summation notation (in terms of \(x^n\) rather than \(x^{n + k}\))
    1. \(\dfrac{1}{1 - x} + \dfrac{1}{1 + x}\)
    2. \(\dfrac{x^3}{1 + 2x}\)
    3. \(\displaystyle \int_{0}^x \frac{1}{1 - t} \; dt = \log\left( \frac{1}{1 - x} \right)\) (hint: take the antiderivative/integral term by term)
    4. \(\dfrac{3}{2 - x}\) (hint: convert to \(\dfrac{a}{1 - bx}\))
    5. \(\dfrac{1 + x}{1 - x^3}\) (hint: split the fraction into two fractions)

  1. Start with \[ \frac{1}{1 - y} = \sum_{n = 0}^\infty y^n \] where maybe \(y = x^3\) and we get \(x^{3n}\) or \(y = -x\) and we get \((-x)^n\).

  2. If we multiply by \(x^3\) and get \(\sum a^n x^{n + 3}\) then subtract \(3\) from \(n\) everywhere to get \(\sum a^{n - 3} x^n\). For the bottom of the summation, we would change from \(n = 0\) to \(n - 3 = 0\) or \(n = 3\).

  3. If we integrate \(\sum x^n\) term by term, we get \(\sum x^{n + 1}{n + 1}\).

  4. Convert to \(\dfrac{3/2}{1 - x/2}\).

  5. You can write your answer as \(\sum a_n x^n\) where \(a_n = \dots\) (formula will depend on if \(n = 3k, 3k + 1, 3k + 2\)).

  1. Convert each sequence to a closed form generating function. Use the most obvious choice of form for the general term of the sequence. Sequences start at \(n = 0\).
    1. \(2, 2, 2, 2, 2, 2, \dots\)
    2. \(0, 1, 0, 1, 0, 1, \dots\)
    3. \(1, 0, 1, 0, 1, 0, \dots\)
    4. \(0, 1, 2, 3, 4, 5, \dots\) (hint: factor out an \(x\) from \(\sum nx^n\) so that the terms are \(\frac{d}{dx} x^n\), then move the derivative operator outside the summation [but after the \(x\) that was factored out])
    5. \(1, 3, 5, 7, 9, 11, \dots\) (hint: use part d)
  1. Write it first as \(\sum 2x^n\) and factor out the \(2\).
  2. Write it first as \(x + x^3 + x^5 + \dots\)
  3. Write it first as \(1 + x^2 + x^4 + \dots\)
  4. \(\displaystyle \frac{d}{dx} \frac{1}{1 - x} = \frac{1}{(1 - x)^2} = \sum nx^{n - 1}\)
  1. Using the formulas from section Section 16.4, find
    1. \(\displaystyle \sum_{n = 0}^\infty \binom{n + 2}{2} x^n\)
    2. \(\displaystyle \sum_{n = 5}^\infty \binom{n - 1}{4} x^n\)
  1. Can be plugged into the formula directly
  2. Look for the formula with \(n - 1\) and then figure out how to choose the right \(k\).
  1. Find the indicated coefficients.
    1. \([x^{10}] \dfrac{1}{1 + 2x}\)
    2. \([x^{20}] \dfrac{1}{(1 - x)^7}\)
    3. \([x^{20}] \dfrac{x^3}{(1 - x)^{10}}\)
    4. \([x^{85}] \dfrac{2x^5}{1 - 3x^5}\) (hint: if the sum is \(\sum (*) x^{5n + 5}\) then the coefficient of \(x^{85}\) occurs where \(5n + 5 = 85\))
  1. Use the formula \(\sum (-2)^n x^n\) and take the coefficient of \(x^{10}\)
  2. Use the formula from Section 16.4.
  3. First use the shift formula from Theorem 17.1 to write it as \([x^{17}] \dfrac{1}{(1 - x)^{10}}\).
  4. The sum is \(\sum 2 \cdot 3^n x^{5n + 5}\)
  1. Write down a generating function for the number of ways to make change for \(n\) dollars using \(1, 5\) and \(10\) dollar bills. (Hint: if we are receiving multiples of \(\$5\) bills, then the generating function should be \(x^0 + x^5 + x^{10} + \cdots\) where the weight function of a bill is its dollar value.)

If the options for $5 bills are \(0, 1, 2, \dots\) then we have \(1 + x^5 + x^{10} + x^{15} + \dots\) where the coefficient gives the number of choices (only 1 way to have \(k\) bills of the same type) and the exponent gives the weight or how much it contributes. You should get geometric series for each bill value.

  1. Repeat the previous problem but now suppose we are only allowed to give out a maximum of one \(\$5\) bill.

Similar to problem 5. but now there are only \(0\) or \(1\) choices for the $5 bill. So \(1 + x^5\) is the generating function for that denomination.

Additional practice

Fill in the blank:

\[ \frac{2}{1 - 3x} \]

is equal to \(\displaystyle \sum_{n = 0}^\infty (\cdots) x^n\).


What is the leading term and common ratio for the generating function whose coefficients are:

\[ 2, -2, 2, -2, 2, -2, 2, -2, 2, -2, \dots ? \]



Hint: the leading term and common ratio might depend on \(x\) after you turn the sequence into \(a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots\).

Solutions
    1. \(\displaystyle \sum_{n = 0}^\infty ((-1)^n + 1) x^n\)
    2. \(\displaystyle \sum_{n = 3}^\infty (-2)^{n - 3}x^n\)
    3. \(\displaystyle \sum_{n = 1}^\infty \frac{x^n}{n}\)
    4. \(\displaystyle \sum_{n = 0}^\infty \frac{3}{2^{n + 1}} x^n\)
    5. \(\displaystyle \sum_{n = 0}^\infty a_n x^n\) where \(a_n = 0\) if \(n = 3k + 2\) and \(a_n = 1\) otherwise (so the sequence \(1, 1, 0, 1, 1, 0, 1, 1, 0, \dots\)).
    1. \(\dfrac2{1 - x}\)
    2. \(\dfrac{x}{1 - x^2}\)
    3. \(\dfrac{1}{1 - x^2}\)
    4. \(\dfrac{x}{(1 - x)^2}\)
    5. \(\displaystyle \sum (2n + 1) x^n = 2\sum n x^n + \sum x^n = \frac{2}{(1 - x)^2} + \frac{1}{1 - x}\).
    1. \(\dfrac{1}{(1 - x)^3}\)
    2. \(\dfrac{x^5}{(1 - x)^5}\)
    1. \((-2)^{10}\)
    2. \(\dbinom{26}{6}\)
    3. \(\dbinom{26}{9}\)
    4. \(2 \cdot 3^{16}\)
  5. \(\dfrac1{(1 - x)(1 - x^5)(1 - x^{10})}\)
  6. \(\dfrac{1 + x^5}{(1 - x)(1 - x^{10})}\)