This article is translated from a Chinese article on my Zhihu account. The original article was posted at 2019-04-06 13:46 +0800.

Notice: Because this article was written very early, there are many mistakes and inappropriate notations.

(I’m going to challenge writing articles without sum symbols!)

In this article, functions all refer to unary functions; both independent and dependent variables are scalars; and differentials refer to ordinary differentials.

Definition 1 (linear differential operator). Let L ⁣(D,x)L\!\left(\mathrm D,x\right) be a differential operator. If for any two functions F1 ⁣(x),F2 ⁣(x)F_1\!\left(x\right),F_2\!\left(x\right) and constants C1,C2C_1,C_2, the operator satisfies

L(C1F2+C2F2)=C1LF1+C2LF2,L\left(C_1F_2+C_2F_2\right)=C_1LF_1+C_2LF_2,

then LL is a linear differential operator.

Lemma 1. The sufficient and necessary condition for LL to be a linear differential operator is that for any tuple of functions F⃗ ⁣(x)\vec F\!\left(x\right) and any tuple of constants C⃗\vec C (the dimensions of the two vectors are the same), the operator satisfies

L(C⃗⋅F⃗)=C⃗⋅LF⃗.L\left(\vec C\cdot\vec F\right)=\vec C\cdot L\vec F.

Brief proof. Directly letting C⃗\vec C and F⃗\vec F be 2-dimensional vectors and using Definition 1, the sufficiency can be proved; by using mathematical induction on the dimension of C⃗\vec C and F⃗\vec F, the necessity can be proved. □\square

Definition 2. an→n=0m≔(a0,a1,…,am)\overrightarrow{a_n}_{n=0}^m\coloneqq\left(a_0,a_1,\ldots,a_m\right).

Lemma 2. Suppose the (m+1)\left(m+1\right)-dimensional vector a⃗\vec a is independent to xx, and {fn ⁣(x)}n=0s\left\{f_n\!\left(x\right)\right\}_{n=0}^s is a sequence of functions, then

Dk(a⃗⋅fn ⁣(x)→n=0s)=a⃗⋅Dkfn ⁣(x)→n=0s.\mathrm D^k\left(\vec a\cdot\overrightarrow{f_n\!\left(x\right)}_{n=0}^s\right) =\vec a\cdot\overrightarrow{\mathrm D^kf_n\!\left(x\right)}_{n=0}^s.

Brief proof. By mathematical induction. □\square

Lemma 3. Suppose P⃗\vec P is a tuple of functions w.r.t. xx, and the dimension of P⃗\vec P is m+1m+1, then the differential operator

L ⁣(D,x)≔P⃗⋅Dk→k=0mL\!\left(\mathrm D,x\right)\coloneqq\vec P\cdot\overrightarrow{\mathrm D^k}^m_{k=0}

is a linear differential operator.

Brief proof. By Definition 1. □\square

Corollary of Lemma 3. Suppose p⃗\vec p is a constant (m+1)\left(m+1\right)-dimensional vector, then the differential operator

L ⁣(D)≔p⃗⋅Dk→k=0mL\!\left(\mathrm D\right)\coloneqq\vec p\cdot\overrightarrow{\mathrm D^k}^m_{k=0} (1)(1)

is a linear differential operator.

Lemma 4 (associativity).

akbk→k=0m⋅ck→k=0m=ak→k=0m⋅bkck→k=0m.\overrightarrow{a_kb_k}_{k=0}^m\cdot\overrightarrow{c_k}_{k=0}^m =\overrightarrow{a_k}_{k=0}^m\cdot\overrightarrow{b_kc_k}_{k=0}^m.

Proof is omitted.

Definition 3 (linear differential operator with constant coefficients). Linear differential operators with form as Equation 1 are called linear differential operators with constant coefficients.

Definition 4 (linear ODE). Suppose LL is a linear differential operator. Then the ODE w.r.t. the function y ⁣(x)y\!\left(x\right)

Ly=fLy=f

is called a linear ODE, where f ⁣(x)f\!\left(x\right) is a function.

Specially, if f=0f=0, the ODE is called a homogeneous linear ODE. If LL is a linear differential operator with constant coefficients, then the ODE is called a linear ODE with constant coefficients.

Definition 5 (generating function). For a sequence {an}n=0∞\left\{a_n\right\}_{n=0}^\infty, the function

G ⁣(x)≔an→n=0∞⋅xn→n=0∞G\!\left(x\right)\coloneqq\overrightarrow{a_n}_{n=0}^\infty\cdot\overrightarrow{x^n}_{n=0}^\infty

is called the (ordinary) generating function (OGF) of the sequence.

Note. here we do not introduce vectors with infinite dimensions. Actually,

G ⁣(x)≔lim⁡s→∞an→n=0s⋅xn→n=0s.G\!\left(x\right)\coloneqq\lim_{s\to\infty}\overrightarrow{a_n}_{n=0}^s\cdot\overrightarrow{x^n}_{n=0}^s.

Definition 6 (exponential generating function). For a sequence {an}n=0∞\left\{a_n\right\}_{n=0}^\infty, the OGF of the sequence {ann!}n=0∞\left\{\frac{a_n}{n!}\right\}_{n=0}^\infty is called the exponential generating function (EGF) of the sequence {an}n=0∞\left\{a_n\right\}_{n=0}^\infty. In other words,

G ⁣(x)≔ann!→n=0∞⋅xn→n=0∞.G\!\left(x\right)\coloneqq\overrightarrow{\frac{a_n}{n!}}_{n=0}^\infty\cdot\overrightarrow{x^n}_{n=0}^\infty.

Lemma 5 (differential of power functions). Suppose n,k∈Nn,k\in\mathbb N, then

Dk(xn)=n!(n−k)!xn−k.\mathrm D^k\left(x^n\right)=\frac{n!}{\left(n-k\right)!}x^{n-k}.

Note. it is stipulated that factorials of negative integers are infinity, so Dk(xn)=0\mathrm D^k\left(x^n\right)=0 when n<kn<k.

Brief proof. By mathematical induction. □\square

Lemma 6 (differential of EGF). If G ⁣(x)G\!\left(x\right) is the EGF of a sequence {an}n=0∞\left\{a_n\right\}_{n=0}^\infty, then DkG\mathrm D^kG is the EGF of {an+k}n=0∞\left\{a_{n+k}\right\}_{n=0}^\infty.

Proof.

DkG=Dk(ann!→n=0∞⋅xn→n=0∞)(Definition 6)=ann!→n=0∞⋅Dk(xn)→n=0∞(Lemma 2)=ann!→n=0∞⋅n!(n−k)!xn−k→n=0∞(Lemma 5)=an(n−k)!→n=0∞⋅xn−k→n=0∞(Lemma 4)=an+kn!→n=0∞⋅xn→n=0∞.(note in Lemma 5)\begin{align*} \mathrm D^kG&=\mathrm D^k\left(\overrightarrow{\frac{a_n}{n!}}_{n=0}^\infty\cdot\overrightarrow{x^n}_{n=0}^\infty\right) &\text{(Definition 6)}\\ &=\overrightarrow{\frac{a_n}{n!}}_{n=0}^\infty\cdot\overrightarrow{\mathrm D^k\left(x^n\right)}_{n=0}^\infty& \text{(Lemma 2)}\\ &=\overrightarrow{\frac{a_n}{n!}}_{n=0}^\infty\cdot\overrightarrow{\frac{n!}{\left(n-k\right)!}x^{n-k}}_{n=0}^\infty& \text{(Lemma 5)}\\ &=\overrightarrow{\frac{a_n}{\left(n-k\right)!}}_{n=0}^\infty\cdot\overrightarrow{x^{n-k}}_{n=0}^\infty& \text{(Lemma 4)}\\ &=\overrightarrow{\frac{a_{n+k}}{n!}}_{n=0}^\infty\cdot\overrightarrow{x^n}_{n=0}^\infty.& \text{(note in Lemma 5)} \end{align*}

Then the result can be proved by Definition 6. □\square

Corollary to Lemma 6.

Dk→k=0m(ann!→n=0∞⋅xn→n=0∞)=an+kn!→n=0∞⋅xn→n=0∞→k=0∞.\overrightarrow{\mathrm D^k}_{k=0}^m\left(\overrightarrow{\frac{a_n}{n!}}_{n=0}^\infty\cdot\overrightarrow{x^n}_{n=0}^\infty\right) =\overrightarrow{\overrightarrow{\frac{a_{n+k}}{n!}}_{n=0}^\infty\cdot\overrightarrow{x^n}_{n=0}^\infty}_{k=0}^\infty.

Lemma 7 (associativity).

a⃗⋅bn,k→k=0m→n=0s⋅c⃗=a⃗⋅bn,k→n=0s⋅c⃗→k=0m.\overrightarrow{\vec a\cdot\overrightarrow{b_{n,k}}_{k=0}^m}_{n=0}^s\cdot\vec c =\vec a\cdot\overrightarrow{\overrightarrow{b_{n,k}}_{n=0}^s\cdot\vec c}_{k=0}^m.

Proof is omitted.

Definition 7 (zero function). The function whose value is always zero whatever the value of the independent variable is is called the zero function.

Lemma 8. The sufficient and necessary condition for the OGF/EGF of a sequence {an}n=0∞\left\{a_n\right\}_{n=0}^\infty to be zero function is that an=0a_n=0 for any nn.

Brief proof. The sufficiency can be proved by Definition 6 and Definition 7; the necessity can be proved by Taylor expansion of the zero function. □\square

Definition 8.

an,k→n=0s→k=0m≔(a0,0a0,1⋯a0,ma1,0a1,1⋯a1,m⋮⋮⋱⋮as,0as,1⋯as,m).\overrightarrow{\overrightarrow{a_{n,k}}_{n=0}^s}_{k=0}^m\coloneqq \left(\begin{matrix} a_{0,0}&a_{0,1}&\cdots&a_{0,m}\\ a_{1,0}&a_{1,1}&\cdots&a_{1,m}\\ \vdots&\vdots&\ddots&\vdots\\ a_{s,0}&a_{s,1}&\cdots&a_{s,m} \end{matrix}\right).

Lemma 9 (distributivity).

p⃗⋅an,k→k=0m→n=0s=an,k→n=0s→k=0mp⃗.\overrightarrow{\vec p\cdot\overrightarrow{a_{n,k}}_{k=0}^m}_{n=0}^s= \overrightarrow{\overrightarrow{a_{n,k}}_{n=0}^s}_{k=0}^m\vec p.

Proof is omitted.

Definition 9 (sequence equation). Let {an}n=0∞\left\{a_n\right\}_{n=0}^\infty be an unknown sequence. If the function F ⁣(n)F\!\left(n\right) explicitly depends on terms in the sequence, then the function

F ⁣(n)=0F\!\left(n\right)=0

is called a sequence equation w.r.t. the sequence {an}n=0∞\left\{a_n\right\}_{n=0}^\infty. For a sequence, if it satisfies the equation for any nn, then it is called a special solution of the sequence equation. The set of all special solutions of the sequence equation is called the general solution of the equation.

Definition 10 (linear dependence of sequences). If for a set of sequences (a sequence of tuples) {a⃗n}n=0∞\left\{\vec a_n\right\}_{n=0}^\infty there exists a tuple of constants C⃗\vec C which are not all zero (the dimensions of C⃗\vec C and a⃗n\vec a_n are the same) such that

C⃗⋅a⃗n=0\vec C\cdot\vec a_n=0

for any nn, then the set of sequences are called to be linearly dependent. They are otherwise called to be linearly independent.

Lemma 10. The sufficient and necessary condition for a set of m+1m+1 sequences {a⃗n}n=0∞\left\{\vec a_n\right\}_{n=0}^\infty to be linearly dependent is that

det⁡a⃗n+k→k=0m=0.\operatorname{det}\overrightarrow{\vec a_{n+k}}_{k=0}^m=0.

Proof. First prove the necessity. There exists a tuple of constants C⃗\vec C which are not all zero such that

C⃗⋅a⃗n=0\vec C\cdot\vec a_n=0

for any nn (Definition 10).

Replace nn by n,n+1,n+1,…,n+mn,n+1,n+1,\ldots,n+m respectively, and we have

C⃗⋅a⃗n+k→k=0m=0⃗.\overrightarrow{\vec C\cdot\vec a_{n+k}}_{k=0}^m=\vec 0.

Let the (l+1)\left(l+1\right)th component of a⃗n\vec a_n be an∗la_n^{*l}, i.e. a⃗n=an∗l→l=0m\vec a_n=\overrightarrow{a_n^{*l}}_{l=0}^m. Then we have

C⃗⋅an∗l→l=0m→k=0m=0⃗.\overrightarrow{\vec C\cdot\overrightarrow{a_n^{*l}}_{l=0}^m}_{k=0}^m=\vec 0.

By Lemma 9, the LHS actually equals an∗l→k=0m→l=0mC⃗\overrightarrow{\overrightarrow{a_{n}^{*l}}_{k=0}^m}_{l=0}^m\vec C.

Define matrix

A≔an∗l→k=0m→l=0m,\mathbf A\coloneqq\overrightarrow{\overrightarrow{a_n^{*l}}_{k=0}^m}_{l=0}^m,

then AC⃗=0⃗\mathbf A\vec C=\vec 0, and

det⁡A=det⁡AT=det⁡a⃗n+k→k=0m.\operatorname{det}\mathbf A=\operatorname{det}\mathbf A^\mathrm T=\det\overrightarrow{\vec a_{n+k}}_{k=0}^m.

Prove by contradiction. Assume that the value of the determinant is not 00, i.e. det⁡A≠0\operatorname{det}\mathbf A\ne0, then the matrix A\mathbf A is invertible. Multiply the equation AC⃗=0⃗\mathbf A\vec C=\vec 0 by A−1\mathbf A^{-1} from the left on both sides, and we have C⃗=0⃗\vec C=\vec 0, which contradicts with the fact that C⃗\vec C is not all zero.

Therefore, det⁡a⃗n+k→k=0m=0\det\overrightarrow{\vec a_{n+k}}_{k=0}^m=0.

(Boohoo! I cannot prove the sufficiency myself.) □\square

Lemma 11. Suppose the sequence equation

p⃗⋅an+k→k=0m=0\vec p\cdot\overrightarrow{a_{n+k}}_{k=0}^m=0

(where p⃗\vec p is a (m+1)\left(m+1\right)-dimensional constant vector and not all zero) has a set of mm linearly independent special solutions {an∗l→l=1m}\left\{\overrightarrow{a_n^{*l}}_{l=1}^m\right\}, then the general solution of the sequence solution is C⃗⋅an∗l→l=1m\vec C\cdot\overrightarrow{a_n^{*l}}_{l=1}^m, where C⃗\vec C is a tuple of mm constants.

Proof. First prove that {an}\left\{a_n\right\}, where

an≔C⃗⋅an∗l→l=1m,a_n\coloneqq\vec C\cdot\overrightarrow{a_n^{*l}}_{l=1}^m,

must be a special solution of the original sequence equation.

Substitute it into the LHS of the original sequence equation, and we have

p⃗⋅C⃗⋅an+k∗l→l=1m→k=0m=C⃗⋅p⃗⋅an+k∗l→k=0m→l=1m(Lemma 7)=C⃗⋅0→l=1m(Definition 9)=0.\begin{align*} \vec p\cdot\overrightarrow{\vec C\cdot\overrightarrow{a_{n+k}^{*l}}_{l=1}^m}_{k=0}^m &=\vec C\cdot\overrightarrow{\vec p\cdot\overrightarrow{a_{n+k}^{*l}}_{k=0}^m}_{l=1}^m& \text{(Lemma 7)}\\ &=\vec C\cdot\overrightarrow0_{l=1}^m& \text{(Definition 9)}\\ &=0. \end{align*}

By Definition 9, the sequence {an}\left\{a_n\right\} is a special solution of the original sequence equation.

Then prove that the original sequence equation does not have a special solution {an}\left\{a_n\right\}, such that there does not exist a set of mm constants C⃗\vec C such that an=C⃗⋅an∗l→l=1ma_n=\vec C\cdot\overrightarrow{a_n^{*l}}_{l=1}^m for any nn.

Prove by contradiction. Assume there is such a special solution, denoted as {an∗0}\left\{a_n^{*0}\right\}. Then by Definition 10, the set of sequences (sequence of tuples) an∗l→l=0m\overrightarrow{a_n^{*l}}_{l=0}^m are linearly independent. Let matrix

A≔an∗l→l=0→k=0m,\mathbf A\coloneqq\overrightarrow{\overrightarrow{a_n^{*l}}_{l=0}}_{k=0}^m,

then according to Lemma 10, A\mathbf A is invertible.

Because the set of sequences are all special solutions of the original sequence equation, by Definition 9,

p⃗⋅an+k∗l→k=0m→l=0m=0⃗.\overrightarrow{\vec p\cdot\overrightarrow{a_{n+k}^{*l}}_{k=0}^m}_{l=0}^m=\vec 0.

By Lemma 9, the LHS of the equation is actually Ap⃗\mathbf A\vec p. Therefore,

Ap⃗=0⃗.\mathbf A\vec p=\vec 0.

Multiply the equation by A−1\mathbf A^{-1} from the left on both sides, we have

p⃗=0⃗,\vec p=\vec 0,

which contradicts with the fact that p⃗\vec p is not all zero.

From all the above, we have proved that the general solution of the sequence equation is C⃗⋅an∗l→l=1m\vec C\cdot\overrightarrow{a_n^{*l}}_{l=1}^m. □\square

Definition 11 (polynomial). Suppose p⃗\vec p is a constant vector whose (m+1)\left(m+1\right)th component is not 00, then the function

F ⁣(x)≔p⃗⋅xk→k=0mF\!\left(x\right)\coloneqq\vec p\cdot\overrightarrow{x^k}_{k=0}^m

is called a polynomial of degree mm w.r.t. xx, and p⃗\vec p is called the coefficients of the polynomial.

Definition 12 (multiplicity). Suppose F ⁣(x)F\!\left(x\right) is an mm-degree polynomial w.r.t. xx, and rr is a complex number, then the maximum natural number w≤mw\le m such that

DqF ⁣(r)→)q=0w−1=0⃗\overrightarrow{\mathrm D^qF\!\left(r\right)})_{q=0}^{w-1}=\vec 0

is called the multiplicity of rr in the polynomial. The complex number with non-zero multiplicity is called a root of the polynomial.

Lemma 12 (fundamental theorem of algebra). The sum of multiplicity of roots of a polynomial equals the degree of the polynomial.

Proof is omitted.

Definition 13 (binomial coefficient).

(uv)≔u!v!(u−v)!.\binom uv\coloneqq\frac{u!}{v!(u-v)!}.

Lemma 13.

If rr is a root with multiplicity ww of the polynomial with coefficients p⃗\vec p, then for any natural number q<wq<w, we have

p⃗⋅k!(k−q)!rk−q→k=0m=0.\vec p\cdot\overrightarrow{\frac{k!}{\left(k-q\right)!}r^{k-q}}_{k=0}^m=0.

Brief proof. First use Definition 11 and Definition 12, and then use Lemma 2 and Lemma 5. □\square

Lemma 14 (Vandermonde’s identity).

(uq−u)→u=0q⋅(ku)→u=0q=(n+kq).\overrightarrow{\binom u{q-u}}_{u=0}^q\cdot\overrightarrow{\binom ku}_{u=0}^q=\binom{n+k}q.

Proof is omitted.

Lemma 15.

(qu)→u=0q⋅n!(n−q+u)!k!(k−u)!→u=0q=(n+k)!(n+k−q)!.\overrightarrow{\binom qu}_{u=0}^q\cdot \overrightarrow{\frac{n!}{\left(n-q+u\right)!}\frac{k!}{\left(k-u\right)!}}_{u=0}^q =\frac{\left(n+k\right)!}{\left(n+k-q\right)!}.

Proof.

(qu)→u=0q⋅n!(n−q+u)!k!(k−u)!→u=0q=q!u!(q−u)!→u=0q⋅n!(n−q+u)!k!(k−u)!→u=0q(Definition 13)=q!n!(q−u)!(n−q+u)!→u=0q⋅k!u!(k−u)!→u=0q(Lemma 4)=q!(nq−u)→u=0q⋅(ku)→u=0q(Definition 13)=q!(n+kq)(Lemma 14)=q!(n+k)!q!(n+k−q)!(Definition 13)=(n+k)!(n+k−q)!.\begin{align*} \overrightarrow{\binom qu}_{u=0}^q\cdot \overrightarrow{\frac{n!}{\left(n-q+u\right)!}\frac{k!}{\left(k-u\right)!}}_{u=0}^q &=\overrightarrow{\frac{q!}{u!\left(q-u\right)!}}_{u=0}^q\cdot \overrightarrow{\frac{n!}{\left(n-q+u\right)!}\frac{k!}{\left(k-u\right)!}}_{u=0}^q& \text{(Definition 13)}\\ &=q!\overrightarrow{\frac{n!}{\left(q-u\right)!\left(n-q+u\right)!}}_{u=0}^q\cdot \overrightarrow{\frac{k!}{u!\left(k-u\right)!}}_{u=0}^q& \text{(Lemma 4)}\\ &=q!\overrightarrow{\binom n{q-u}}_{u=0}^q\cdot \overrightarrow{\binom ku}_{u=0}^q& \text{(Definition 13)}\\ &=q!\binom{n+k}q& \text{(Lemma 14)}\\ &=q!\frac{\left(n+k\right)!}{q!\left(n+k-q\right)!}& \text{(Definition 13)}\\ &=\frac{\left(n+k\right)!}{\left(n+k-q\right)!}. \end{align*} □\square

Lemma 16. If rr is a root with multiplicity ww of the polynomial with coefficients p⃗\vec p, then for any natural number q<wq<w, the sequence

an≔n!(n−q)!rn−qa_n\coloneqq\frac{n!}{\left(n-q\right)!}r^{n-q} (2)(2)

is a special solution of the sequence equation p⃗⋅an+k→k=0m=0⃗\vec p\cdot\overrightarrow{a_{n+k}}_{k=0}^m=\vec 0.

Proof. Because

an+k=(n+k)!(n+k−q)!rn+k−q,a_{n+k}=\frac{\left(n+k\right)!}{\left(n+k-q\right)!}r^{n+k-q},

we have

an+krn+k−q=(n+k)!(n+k−q)!=(qu)→u=0q⋅n!(n−q+u)!k!(k−u)!→u=0q(Lemma 15)=r−k(k!(k−u)!→u=0q⋅(qu)n!(n−q+u)!ru→u=0q),(Lemma 4)\begin{align*} \frac{a_{n+k}}{r^{n+k-q}}&=\frac{\left(n+k\right)!}{\left(n+k-q\right)!}\\ &=\overrightarrow{\binom qu}_{u=0}^q\cdot \overrightarrow{\frac{n!}{\left(n-q+u\right)!}\frac{k!}{\left(k-u\right)!}}_{u=0}^q& \text{(Lemma 15)}\\ &=r^{-k}\left(\overrightarrow{\frac{k!}{\left(k-u\right)!}}_{u=0}^q\cdot \overrightarrow{\binom qu\frac{n!}{\left(n-q+u\right)!}r^u}_{u=0}^q\right),& \text{(Lemma 4)} \end{align*}

and thus

an+k=rn−q(k!(k−u)!rk−u→u=0q⋅(qu)n!(n−q+u)!ru→u=0q).a_{n+k}=r^{n-q}\left(\overrightarrow{\frac{k!}{\left(k-u\right)!}r^{k-u}}_{u=0}^q\cdot \overrightarrow{\binom qu\frac{n!}{\left(n-q+u\right)!}r^u}_{u=0}^q\right).

Because the LHS of the original sequence equation

p⃗⋅an+k→k=0m=p⃗⋅rn−q(k!(k−u)!rk−u→u=0q⋅(qu)n!(n−q+u)!ru→u=0q)→k=0m=rn−q(qu)n!(n−q+u)!ru→u=0q⋅p⃗⋅k!(k−u)!rk−u→u=0q→k=0m(Lemma 7)=rn−qn!(n−q+u)!ru→u=0q⋅0→k=0m(Lemma 13)=0,\begin{align*} \vec p\cdot\overrightarrow{a_{n+k}}_{k=0}^m &=\vec p\cdot\overrightarrow{r^{n-q}\left(\overrightarrow{\frac{k!}{\left(k-u\right)!}r^{k-u}}_{u=0}^q\cdot \overrightarrow{\binom qu\frac{n!}{\left(n-q+u\right)!}r^u}_{u=0}^q\right)}_{k=0}^m\\ &=r^{n-q}\overrightarrow{\binom qu\frac{n!}{\left(n-q+u\right)!}r^u}_{u=0}^q\cdot \overrightarrow{\vec p\cdot\overrightarrow{\frac{k!}{\left(k-u\right)!}r^{k-u}}_{u=0}^q}_{k=0}^m& \text{(Lemma 7)}\\ &=r^{n-q}\overrightarrow{\frac{n!}{\left(n-q+u\right)!}r^u}_{u=0}^q\cdot \overrightarrow{0}_{k=0}^m& \text{(Lemma 13)}\\ &=0, \end{align*}

by Definition 9, {an}\left\{a_n\right\} is a special solution of the sequence equation. □\square

Lemma 17. The sequence

an≔Cl,q→q=0wl−1⋅n!(n−q)!rln−q→q=0wl−1→l=1o⋅1⃗a_n\coloneqq\overrightarrow{\overrightarrow{C_{l,q}}_{q=0}^{w_l-1}\cdot \overrightarrow{\frac{n!}{\left(n-q\right)!}r_l^{n-q}}_{q=0}^{w_l-1}}_{l=1}^o\cdot\vec 1

is the general solution to the sequence equation p⃗⋅an+k→k=0m=0\vec p\cdot\overrightarrow{a_{n+k}}_{k=0}^m=0, where rl→l=1o\overrightarrow{r_l}_{l=1}^o all different roots of the polynomial with coefficients p⃗\vec p, and wl→l=1o\overrightarrow{w_l}_{l=1}^o are the corresponding multiplicities of the roots, and Cl,qC_{l,q} are arbitrary constants.

Brief proof. By Lemma 16, the root rlr_l brings wlw_l special solutions. All the special solutions brought by all the roots can be proved to be linearly independent. According to Lemma 12, there are mm linearly independent special solutions. According to Lemma 11, the result can be proved. □\square

Lemma 18. The sufficient and necessary condition for the sequence {an}\left\{a_n\right\} to be a special solution of the sequence equation p⃗⋅an+k→k=0m=0\vec p\cdot\overrightarrow{a_{n+k}}_{k=0}^m=0 is that its EGF is a special solution of the ODE

p⃗⋅Dk→k=0my=0.\vec p\cdot\overrightarrow{\mathrm D^k}_{k=0}^m y=0.

Proof. First prove the sufficiency. Suppose yy is the EGF of {an}\left\{a_n\right\}, i.e.

y=ann!→n=0∞⋅xn→n=0∞y=\overrightarrow{\frac{a_n}{n!}}_{n=0}^{\infty}\cdot\overrightarrow{x^n}_{n=0}^\infty

(Definition 6), then the LHS of the original ODE

L ⁣(D)y=p⃗⋅Dk→k=0m(ann!→n=0∞⋅xn→n=0∞)=p⃗⋅an+kn!→n=0∞⋅xn→n=0∞→k=0m(Lemma 6)=p⃗⋅an+kn!→k=0m→n=0∞⋅xn→n=0∞(Lemma 7)=p⃗⋅an+k→k=0mn!→n=0∞⋅xn→n=0∞.\begin{align*} L\!\left(\mathrm D\right)y &=\vec p\cdot\overrightarrow{\mathrm D^k}_{k=0}^m \left(\overrightarrow{\frac{a_n}{n!}}_{n=0}^{\infty}\cdot\overrightarrow{x^n}_{n=0}^\infty\right)\\ &=\vec p\cdot\overrightarrow{\overrightarrow{\frac{a_{n+k}}{n!}}_{n=0}^\infty\cdot\overrightarrow{x^n}_{n=0}^\infty}_{k=0}^m& \text{(Lemma 6)}\\ &=\overrightarrow{\vec p\cdot\overrightarrow{\frac{a_{n+k}}{n!}}_{k=0}^m}_{n=0}^\infty\cdot \overrightarrow{x^n}_{n=0}^\infty& \text{(Lemma 7)}\\ &=\overrightarrow{\frac{\vec p\cdot\overrightarrow{a_{n+k}}_{k=0}^m}{n!}}_{n=0}^\infty\cdot \overrightarrow{x^n}_{n=0}^\infty. \end{align*}

Therefore, L ⁣(D)yL\!\left(\mathrm D\right)y is the EGF of the sequence {p⃗⋅an+k→k=0m}n=0∞\left\{\vec p\cdot\overrightarrow{a_{n+k}}_{k=0}^m\right\}_{n=0}^\infty. Because it is a zero function, by Lemma 8, for any nn,

p⃗⋅an+k→k=0m=0.\vec p\cdot\overrightarrow{a_{n+k}}_{k=0}^m=0.

All the steps are reversible, so the necessity is also proved. □\square

Definition 14 (exponential function). The EGF of the sequence {1}\left\{1\right\} is called the exponential function, i.e.

ex≔1n!→n=0∞⋅xn→n=0∞.\mathrm e^x\coloneqq\overrightarrow{\frac 1{n!}}_{n=0}^{\infty}\cdot\overrightarrow{x^n}_{n=0}^\infty.

Lemma 19. If yy is the EGF of the sequence in Equation 2, then y=xqerxy=x^q\mathrm e^{rx}.

Proof.

y=n!(n−q)!n!→n=0∞⋅xn→n=0∞(Definition 6)=rn−q(n−q)!→n=0∞⋅xn→n=0∞=rnn!→n=0∞⋅xn+q→n=0∞(note of Lemma 5)=xq1n!→n=0∞⋅(rx)n→n=0∞(Lemma 4)=xqerx.(Definition 14)\begin{align*} y&=\overrightarrow{\frac{\frac{n!}{\left(n-q\right)!}}{n!}}_{n=0}^{\infty}\cdot\overrightarrow{x^n}_{n=0}^\infty& \text{(Definition 6)}\\ &=\overrightarrow{\frac{r^{n-q}}{\left(n-q\right)!}}_{n=0}^{\infty}\cdot\overrightarrow{x^n}_{n=0}^\infty\\ &=\overrightarrow{\frac{r^n}{n!}}_{n=0}^{\infty}\cdot\overrightarrow{x^{n+q}}_{n=0}^\infty& \text{(note of Lemma 5)}\\ &=x^q\overrightarrow{\frac 1{n!}}_{n=0}^{\infty}\cdot\overrightarrow{\left(rx\right)^n}_{n=0}^\infty& \text{(Lemma 4)}\\ &=x^q\mathrm e^{rx}.& \text{(Definition 14)} \end{align*} □\square

Corollary of Lemma 18 and 19. The function

y=Cl,q→q=0wl−1⋅xq→q=0wl−1erlx→l=1o⋅1⃗y=\overrightarrow{\overrightarrow{C_{l,q}}_{q=0}^{w_l-1}\cdot\overrightarrow{x^q}{q=0}^{w_l-1}\mathrm e^{r_lx}}_{l=1}^o\cdot\vec 1

is the general solution of the ODE

p⃗⋅Dk→k=0my=0,\vec p\cdot\overrightarrow{\mathrm D^k}_{k=0}^m y=0,

where rl→l=1o\overrightarrow{r_l}_{l=1}^o are the different roots of the polynomial with coefficients p⃗\vec p, and wl→l=1o\overrightarrow{w_l}_{l=1}^o are the corresponding multiplicities of the roots, and Cl,qC_{l,q} are arbitrary constants.

Finally, according to all the lemmas above, we now know how to solve the ODE

p⃗⋅Dk→k=0my=0,\vec p\cdot\overrightarrow{\mathrm D^k}_{k=0}^m y=0,

where the (m+1)\left(m+1\right)th component of p⃗\vec p is not zero. Actually, all we need to do is to solve the polynomial with coefficients p⃗\vec p, and use the corollary above, and then we can get the general solution of the original ODE.

The method is identical to that in Advanced Mathematics (notes of translation: this is a popular book in China about calculus), but the derivation is different. Although mine is much more complex, but it is very interesting, because it involves much knowledge in algebra.

(I haven’t used the summation symbol! I’m so good!

The whole article is using the scalar product of vectors as summation, very entertaining. Actually, when examining linear problems, vectors are good. Also, it looks clear if I use the vector notation.)