Skip to content

Homework 6

Combi_hw_6_spring_2025.pdf

  1. Find the inverse of the formal power series from \(C[[s]]\) for a series given by \(\sum_{k=0}^{\infty} (k + 1) s^k\)

    Express the answer in the form \(\sum_{k=0}^{\infty} c_k s^k\)

    Solution

    Since we know \((1+s)^\alpha = \sum_{n=0}^\infty \binom{\alpha}{n} s^n = \sum_{n=0}^\infty \frac{(\alpha)_n}{n!} s^n\)
    Then we need \(n+1 = \frac{(\alpha)_n}{n!} \implies \alpha=-2\) and \((1-s)^\alpha\)
    Then \((1-s)^{-2} = 1+2s+3s^2 + \dots + (k+1)s^k + \dots = \sum_{k=0}^\infty (k+1)s^k\)
    \(\implies \frac{1}{(1-s)^2} = \sum_{k=0}^\infty (k+1)s^k\)

    Thus the inverse of this formal power series is \((1-s)^{2}=1-2s+s^2\)​

  2. Using the generating function for the Fibonacci numbers, prove the following identities:

    • \(f_{0} + f_{1} + \cdots + f_{n} = f_{n+2}- 1\)
    • \(f_{0} + f_{2} + \cdots + f_{2n}= f_{2n+1}\)​
    • \(f_{1} + f_{3} + \cdots + f_{2n-1}= f_{2n}- 1\)

    Here \(f_0 = f_1 = 1\).

    Solution

    Since \(F(s) = \frac{1}{1-s-s^2} = \sum_{k=0}^\infty f_k s^k\)

    • The left hand side is \(\sum_{k=0}^n f_k\), then the corresponding generating function is \(\sum_{k=0}^\infty (\sum_{m=0}^k f_m) s^k\) (when \(k=n\), \(\sum_{m=0}^n f_m s^n\))
      Then \(L(s) = \sum_{k=0}^\infty (\sum_{m=0}^k f_m) s^k = F(s) \cdot \frac{1}{1-s} = \frac{1}{(1-s-s^2)(1-s)} = \frac{s+2}{1-s-s^2} - \frac{1}{1-s}\)
      ​\(= \sum_{k=0}^\infty (2f_{k} + f_{k-1}) s^k - \sum_{k=0}^\infty s^k\)
      Then the coefficient at \(n\) is \(2f_{n}+f_{n-1}-1=f_{n+1}+f_{n}-1=f_{n+2}-1\)
      Thus, they are equal
    • The left hand side is \(\sum_{k=0}^n f_{2k}\), the corresponding generating function: \(\sum_{k=0}^\infty (\sum_{m=0}^k f_{2m}) s^k\)
      ​\(F(s) = f_0 + f_1 s + f_2 s^2 + f_3 s^3 + f_4 s^4 + f_5 s^5 + f_6 s^6 + \dots\)
      ​\(F(s^{1/2}) = f_0 + f_1 s^{1/2} + f_2 s + f_3 s^{3/2} + f_4 s^2 + f_5 s^{5/2} + f_6 s^3 + \dots\)
      ​\(F(-s^{1/2}) = f_0 - f_1 s^{1/2} + f_2 s - f_3 s^{3/2} + f_4 s^2 - f_5 s^{5/2} + f_6 s^3 + \dots\)
      Then \(F(s^{1/2}) + F(-s^{1/2}) = 2 \sum_{k=0}^\infty f_{2k} s^k\), then \(\sum_{k=0}^\infty f_{2k} s^k = \frac{F(s^{1/2}) + F(-s^{1/2})}{2}\) \(=\frac{\frac{1}{1-s^{1/2}-s}+\frac{1}{1+s^{1/2}-s}}{2}=\frac{1-s}{1-3s+s^{2}}\)
      Then \(\sum_{k=0}^{\infty}(\sum_{m=0}^{k}f_{2m})s^{k}=\sum_{k=0}^{\infty}f_{2k}s^{k}\times \sum_{k=0}^{\infty}s^{k}=\frac{1-s}{1-3s+s^{2}}\times\frac{1}{1-s}=\frac{1}{1-3s+s^{2}}\)
      Similarly for right hand side: \(F(s^{1/2}) - F(-s^{1/2}) = 2 f_{1} s^{1/2}+ 2 f_{3} s^{3/2}+ \dots\)
      ​\(f_1 s^{1/2} + f_3 s^{3/2} + f_5 s^{5/2} + \dots = \frac{F(s^{1/2}) - F(-s^{1/2})}{2}\)
      ​\(f_{1}+f_{3}s+f_{5}s^{2}+\dots=\frac{F(s^{1/2})-F(-s^{1/2})}{2s^{1/2}}=\frac{\frac{1}{1-s^{1/2}-s}-\frac{1}{1+s^{1/2}-s}}{2s^{1/2}} =\frac{1}{1-3s+s^{2}}\)
      Thus \(\sum_{k=0}^\infty f_{2k+1} s^k = \frac{1}{1-3s+s^2}\). Thus the equality holds.
    • From identity 2 we got \(f_1 + f_3 s + f_5 s^2 + \dots = \frac{1}{1-3s+s^2}\)
      Then \(s(f_1 + f_3 s + f_5 s^2 + \dots) = \frac{s}{1-3s+s^2}\), then \(\sum_{k=1}^\infty (\sum_{m=1}^k f_{2m-1}) s^k = \frac{s}{1-3s+s^2} \times \frac{1}{1-s}\)
      Also we know \(\sum_{k=0}^\infty f_{2k} s^k = \frac{1-s}{1-3s+s^2}\) above, then \(\sum_{k=0}^\infty (f_{2k} - 1) s^k = \frac{1-s}{1-3s+s^2} - \frac{1}{1-s}\) \(=\frac{s}{1-4s+4s^{2}-s^{3}}\)
      ​\(= \frac{s}{1-3s+s^2} \times \frac{1}{1-s} = \sum_{k=1}^\infty (\sum_{m=1}^k f_{2m-1}) s^k\)
      Thus the equality holds.

  3. Find the generating functions and explicit expressions for the sequence given by the recurrence relation:
    ​\(a_{n+3} = 2a_{n+1} - a_n, \quad a_0 = 1, \quad a_1 = -1, \quad a_2 = 2\)

    By general recursion formula: \(F(s) = \frac{P(s)}{1-2s^2+s^3}\)
    By decomposition theorem: \(\frac{P(s)}{1-2s^{2}+s^{3}}=\frac{-A}{1-s}+\frac{-B}{\frac{1-\sqrt{5}}{2}-s}+\frac{-C}{\frac{1+\sqrt{5}}{2}-s} =\frac{-A}{1-s}+\frac{-\frac{2B}{1-\sqrt{5}}}{1-\frac{2}{1-\sqrt{5}}s}+\frac{-\frac{2C}{1+\sqrt{5}}}{1-\frac{2}{1+\sqrt{5}}s}\)
    Then \(\sum_{n=0}^{\infty}[-A-\left(\frac{2}{1-\sqrt{5}}\right)^{n}\frac{2B}{1-\sqrt{5}} -\left(\frac{2}{1+\sqrt{5}}\right)^{n}\frac{2C}{1+\sqrt{5}}]s^{n}=\sum_{n=0}^{\infty} [-A-\left(\frac{2}{1-\sqrt{5}}\right)^{n+1}B-\left(\frac{2}{1+\sqrt{5}}\right)^{n+1} C]s^{n}\)
    When \(n=0\), \(a_{0}=-1=A+\frac{2B}{1-\sqrt{5}}+\frac{2C}{1+\sqrt{5}}\)
    When \(n=1\), \(a_{1}=1=A+\frac{2}{3-\sqrt{5}}B+\frac{2}{3+\sqrt{5}}C\)
    When \(n=2\), \(a_{2}=-2=A+\left(-2-\sqrt{5}\right)B+\left(-2+\sqrt{5}\right)C\)
    Then \(A = 0\), \(B = \frac{\sqrt{5}}{5}\), \(C = -\frac{\sqrt{5}}{5}\).

    After calculation: \(P(s)=1-s\), then \(F(s)=\frac{1}{1+s-s^{2}}=\sum_{n=0}^{\infty}\frac{\left(-1\right)^{n+1}}{\sqrt{5}} \left[\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1+\sqrt{5}}{2}\right)^{n+1} \right]s^{n}\)​

  4. Let \(A(s) = \sum_{k=0}^{\infty} a_k s^k, \quad B(s) = \sum_{k=0}^{\infty} b_k s^k, \quad C(s) = \sum_{k=0}^{\infty} c_k s^k\)

    • Express \(A(s)\) via \(B(s)\) if \(b_n = \sum_{k=0}^{n} a_k\)

    Since \(b_n = \sum_{k=0}^{n} a_k\), then \(\left\{ \begin{array}{l} b_0=a_0 \\ b_1=a_0+a_1 \\ \vdots \\ b_{n}=a_0+\cdots+a_{n} \end{array}\right.\implies\left\{ \begin{array}{l} a_0=b_0 \\ a_1=b_1-b_0 \\ \vdots \\ a_{n}=b_{n}-b_{n-1} \end{array}\right.\)​
    Then \(A(s)=\sum_{k=0}^{\infty}(b_{k}-b_{k-1})s^{k}=\sum_{k=0}^{\infty}b_{k}s^{k}-\sum_{k=0} ^{\infty}b_{k-1}s^{k}\)
    ​\(\sum_{k=0}^{\infty}b_{k}s^{k}-s\sum_{k=0}^{\infty}b_{k-1}s^{k-1}=B\left(s\right) -sB\left(s\right)=\left(1-s\right)B\left(s\right)\) - Express \(C(s)\) via \(A(s)\) and \(B(s)\) if \(c_n = \sum_{j+2k=n} a_j b_k\)

    \(A(s) = \sum_{n=0}^{\infty} a_n s^n\), \(B(s) = \sum_{n=0}^{\infty} b_n s^n\), \(B(s^{2})=\sum_{n=0}^{\infty}b_{n}s^{2n}\)
    Then \(C(s)=A(s)\cdot B(s^{2})=\sum_{n=0}^{\infty}(\sum_{j+2k=n}a_{j}b_{k})s^{n}\) by Cauchy product. - Express \(C(s)\) via \(A(s)\) and \(B(s)\) if \(c_n = \sum_{j+2k \leq n} a_j b_k\)

    Since \(A(s)B(s^{2})=\sum_{n=0}^{\infty}(\sum_{j+2k=n}a_{j}b_{k})s^{n}\), then \(\sum_{n=0}^{\infty}(\sum_{j+2k=n}a_{j}b_{k})s^{n}\times(\sum_{n=0}^{\infty}s^{n} )=\sum_{n=0}^{\infty}(\sum_{j+2k\leq n}a_{j}b_{k})s^{n}\) by Cauchy Product.
    Then \(C(s)=A(s)\cdot B(s^{2})\cdot\frac{1}{1-s}\)

‍