Eikonal Blog

2012.11.26

Generating functions

Filed under: fun, mathematics, number theory — Tags: , , , , , , , , , , , , , , , , , , , — sandokan65 @ 13:53

Recently I have been rereading the Herbert S. Wilf’s free online book Generatingfunctionology – http://www.math.upenn.edu/~wilf/DownldGF.html. It is choke-full of interesting results.

Definitions

For a number series {\bf a} :\equiv \{a_n|n\in\{0,\infty\}\} one defines following generating functions (GFs):

  • Ordinary Power Series GF (OPSGF): OPSGF[a](x) :\equiv \sum_{n=0}^\infty a_n x^n \leftrightarrow_{opsgf} {\bf a};
  • Exponential Series GF (EGF): EGF[a](x) :\equiv \sum_{n=0}^\infty a_n \frac{x^n}{n!} \leftrightarrow_{egf} {\bf a};
  • Dirichlet GF (DGF): DGF(x;s) :\equiv \sum_n \frac{a_n}{n^s} x^n \leftrightarrow_{dgf} {\bf a};
  • Lambert GF (LGF): LGF(x) :\equiv \sum_n \frac{a_n}{1-x^n} x^n \leftrightarrow_{lgf} {\bf a};
  • Bell GF (BGF): BGF(x;s) :\equiv \sum_n a_{p^n} x^n \leftrightarrow_{bgf} {\bf a};
  • Poisson GF (PGF): PGF(x;s) :\equiv \sum_n \frac{a_n}{n!} x^n e^{-x} = e^{-x} EGF(x) \leftrightarrow_{pgf} {\bf a};

Simple results

  • \{a_n=n\} \leftrightarrow_{opsgf} f(x) = \frac{x}{(1-x)^2}.
  • \{a_n=n^2\} \leftrightarrow_{opsgf} f(x) = \frac{x(x+1)}{(1-x)^3}.
  • \{a_n=b^n\} \leftrightarrow_{opsgf} f(x) = \frac{1}{1-b x}.
  • \{a_n=n\} \leftrightarrow_{egf} f(x) = x e^{x}.
  • \{a_n=n^2\} \leftrightarrow_{egf} f(x) = x(x+1)e^{x}.
  • \{a_n=b^n\} \leftrightarrow_{egf} f(x) = e^{b x}.
  • For Fibonacci numbers \{F_n|F_{n+1} = F_n + F_{n-1} | f_0 = F_1 = 1\} one has: OPSGF(x) = \frac{x}{1-x-x^2}, leading to F_n = \frac{r_+^n-(r_-^n}{\sqrt{5}} (r_\pm = \frac{1\pm\sqrt{5}}{2}).
  • \{a_n|a_{n+1}=2 a_n + 1| a_0=0\} \leftrightarrow_{opsgf} OPSGF = \frac{x}{(1-x)(1-2x)} = \frac{1}{1-2x} - \frac{1}{1-x}; which leads to a_n=2^n - 1.
  • For a_{n+1} = 2 a_n + n, $alatex _0=1$ one has: OPSGF = \frac{2}{1-2x} - \frac1{(1-x)^2} leading to
    a_n = 2^{n-1} - n - 1.

Define [x^n]f(x) as the coefficient next to x^n in power series f(x). Examples and properties:

  • [x^n] e^x = \frac1{n!},
  • [x^n] \frac1{1-ax} = a^n,
  • [x^n] (1+x)^s = \binom{s}{n},
  • [x^n] \{x^m f(x)\} = [x^{n-m}] f(x),
  • [\lambda x^n] f(x) = \frac1{\lambda} [x^n]f(x),
  • \left[\frac{x^n}{n!}\right] e^x = 1.

For binomial coeficients:

  • \sum_{k=0}^{\infty} \binom{n}{k} x^k = (1+x)^n,
  • \sum_{n=0}^{\infty} \binom{n}{k} y^n = \frac{y^k}{(1-y)^{k+1}},
  • \binom{n}{k} = [x^k y^n] \frac1{1 - y (1+x)}.

Some orthogonal polynomials:

  • Tchebitshev polynomials generating function: \sum_{n=0}^\infty \frac{z^n}{n!} T_n(x) = e^{zx}\cos(z\sqrt{1-x^2}).
  • Legendre polynomials generating function: \frac1{(1-2tz+z^2)^{\frac12}} = \sum_{n=0}^\infty P_n(t)z^n.
  • Generating function for associated Legendre polynomials: (1-2tc+t^2)^{\alpha} = |1-t e^{i\theta}|^{2\alpha} = \sum_{n=0}^\infty t^n P_n^{\alpha}(c).

Dirichlet series generating functions

  • For a_n=1: DGF = \zeta(s).
  • For a_n=\mu(n) (the Moebius function): DGF = \frac1{\zeta(s)}.
  • For a_n=d(n)=\sigma_0(n) (the zeroth-order divisor function): DGF = \zeta(s)^2.
  • For a_n=\sigma_k(n) (the kth-order divisor function): DGF = \zeta(s)\zeta(s-k).
  • For a_n=\phi(n) (the totient function): DGF = \frac{\zeta(s-1)}{\zeta(s)}.
  • For a_n=H(n) (the number of ordered factorizations): DGF = \frac{1}{2 - \zeta(s)}.
  • For a_n=\frac12 [1-(-1)^n]: DGF = \lambda(s) (the Dirichlet lambda function).

Moebius inversion formula:

  • If two DGF series A(s) and B(s) have coefficient relation a_n = \sum_{d|n} b_d, then A(s) = B(s) \zeta(s), and b_n = \sum_{d|n} \mu\left(\frac{n}{d}\right) a_d.
  • If a_n = \sum_{d|n} b_d, then b_n = \sum_{d|n} \mu\left(\frac{n}{d}\right) a_d.

2010.03.12

Fibonacci numbers – simple generalizations

Filed under: mathematics — Tags: , , , — sandokan65 @ 17:32

Source: 2009.02.04 Wed

The Fibonacci series \{f_n | n\in {\Bbb N}_0\} are defined by the recursive equation

    f_{n} = f_{n-1} + f_{n-2}

and the “initial conditions” (i.e. known) f_0 and f_1.

The case f_0=f_1=1 is the original Fibonacci’s sequence, and traditionally the members of the sequence are symbolized by capital case F: \{F_0=1, F_1=1, F_2=2, \cdots\}.

The exponential-type generating function {\cal F}(z) :\equiv \sum_{n=0}^\infty \frac{z^n}{n!} f_n satisfies the simple IVP (Initial value Problem):

  • {\cal F}''(z) = {\cal F}'(z) + {\cal F}(z),
  • {\cal F}(0) = f_0,
  • {\cal F}'(0) = f_1,

with the unique solution

    {\cal F}(z) = \frac{f_0}{\sqrt{5}} [(\varphi-1) e^{+\varphi z} + \varphi e^{(1-\varphi) z} ] + \frac{f_1}{\sqrt{5}} [e^{+\varphi z} - e^{(1-\varphi) z}].

Here $\varphi :\equiv \frac{\sqrt{5}+1}2$ is the Golden Section, a root of the characteristic polynomial $P(\lambda) = \lambda^2 – \lambda-1$ (the other solution being $1-\varphi = \frac{\sqrt{5}-1}2$).

Having the explicit expression for the generating function, one gets the explicit expression for individual sequence members:

    f_n = \varphi^n \frac{(1-\varphi) f_0 + f_1}{\sqrt{5}} + (1-\varphi)^n \frac{\varphi f_0 - f_1}{\sqrt{5}}.

First slight generalization

Use the recursive equation f_{n+2} = m f_{n+1} + k f_n. It leads to the following ODE for the generating function {\cal F}''(z) = m {\cal F}'(z) + k {\cal F}(z), the characteristic root equation \lambda^2 = m \lambda + k with the solutions \lambda_\pm = \frac{m\pm \kappa}2 (where \kappa :\equiv \sqrt{m^2+4 k}). The solution for the generating function is

    {\cal F}(z) = f_0 \left[\frac{1-m}2 e^{\lambda_+ z} - \frac{1+m}2 e^{\lambda_- z}\right] + f_1 \left[e^{\lambda_+ z} - e^{\lambda_- z}\right]

and the explicit expression for the sequence members is

    f_n = f_0 \left[\frac{1-m}2 (\lambda_+)^n - \frac{1+m}2 (\lambda_-)^n\right] + f_1 \left[(\lambda_+)^n - (\lambda_-)^n\right].

Second slight generalization

Use the recursive equation f_{n+3} = f_{n+3} + f_{n+1} + f_n. Here:

Blog at WordPress.com.