Linear Recurrence Relations and Differential Equations

 by Lenard Wu

How to understand linear recurrence relations and differential equations properly?

1. What is the method in A-level to find the general formula of recurrence relation:

an=uan−1+van−2

Step1: Find the characteristic equation and find the roots x2−ux−v=0 x1,x2=u±√u2+4v2

Step2: If u2+4v > 0 ,which means 𝑥1≠𝑥2

Then an= λ𝑥1𝑛 + μ𝑥2𝑛 ,λ and μ are constant determined by given a0 and a1.

If u2+4v = 0 ,which means 𝑥1=𝑥2 = x

Then an=( λ + μ*n)𝑥𝑛 ,λ and μ are constant determined by given a0 and a1.

If u2+4v < 0 ,which means 𝑥1≠𝑥2 are complex

Then an= λ𝑥1𝑛 + μ𝑥2𝑛 ,λ and μ are constant determined by given a0 and a1.

While in this case , we can use De Movire’s theorem:

𝑥1𝑛=𝑟𝑛(𝑐𝑜𝑠(𝑛𝜃)+𝑖𝑠𝑖𝑛(𝑛𝜃))

We can find the final formula is with trigonometric function.

2. What is the method in A-level to find the solutions of second-order homogeneous differential equation

𝑑2𝑦𝑑𝑥2+𝑢𝑑𝑦𝑑𝑥+ vy =0

Step1: Find the characteristic equation and find the roots λ2+uλ+v=0 λ1,λ2=−u±√u2−4v2

Step2: If u2−4v > 0 ,which means λ1≠λ2

Then y= c1𝑒λ1𝑥 + c2eλ2x , c1and c2 are constant determined by initial conditions.

If u2−4v = 0 ,which means λ1=λ2=λ

Then y=（c1+ c2x）eλx ,c1and c2 are constant determined by initial conditions.

If u2−4v < 0 ,which means λ1≠λ2 are complex

Then y= c1𝑒λ1𝑥 + c2eλ2x , c1and c2 are constant determined by initial conditions.

While in this case , we can use Euler Formula:

𝑒𝑖𝜃=𝑐𝑜𝑠𝜃+ isin𝜃

We can find the final solution is with trigonometric function.

3. If the two questions above are non-homogeneous, we know the final solution is the sum of general solution and particular solution.

4. If the two questions above are nth- order, according to fundamental algebra theorem, we can always find n roots in complex field.

BUT WHY ARE THESE METHODS SO SIMILAR?

WHAT DO THESE METHODS REPRESENT FOR?

EXPLAIN FROM LINEAR ALGEBRA 1.A vector space over a field F is a set V together with two binary operations that satisfy the eight axioms listed below. In the following, V × V denotes the set of the ordered pairs of elements of V (that is, the Cartesian product of V with itself), and → denotes a mapping from one set to another. In this context, the elements of V are commonly called vectors, and the elements of F are called scalars.

· The first operation, called vector addition or simply addition + : V × V → V, assigns to any two vectors v and w in V a third vector in V which is commonly written as v + w, and called the sum of these two vectors. · The second operation, called scalar multiplication F × V → V， assigns to any scalar a in F and any vector v in V another vector in V, which is denoted av. (Scalar multiplication is not to be confused with the scalar product, which is an additional operation on some specific vector spaces, called inner product spaces. Scalar multiplication is a multiplication of a vector by a scalar that produces a vector, while the scalar product is a multiplication of two vectors that produces a scalar.) For having a vector space these two operations must satisfy the eight axioms, which are listed in the following table below, where the equations must be satisfied for every u, v and w in V, and a and b in F.

2. Obviously ,not only the vector we learned in geometry ,but also some interesting stuff can be considered as a vector ,like sequence and smooth functions(prove it by yourself!).Hence define a vector space V consists of elements which are all sequence with a certain second-order recurrence relation : an=an−1+an−2. Since the first two term determine the whole sequence, we can set (a0 ,a1) is bijective to a satisfied sequence, while (a0 ,a1) ∈R2 is bijective to V,thus V is a 2 dimension space.

Dim(V)=2

3. If we try to find the general formula of Fibonacci sequence, which is (0,1) in R2,we should find the coordinate in V. Hence the first step is to determine the bases of V ,a good idea is to find a well-property series such as geometric series.

4. Now put nth,n-1th and n-2th terms into relations

Axiom Meaning

Associativity of vector addition u + (v + w) = (u + v) + w

Commutativity of vector addition u + v = v + u

Identity element of vector addition There exists an element 0 ∈ V, called the zero vector, such that v + 0 = v for all v ∈ V.

Inverse elements of vector addition For every v ∈ V, there exists an element −v ∈ V, called the additive inverse of v, such that v + (−v) = 0.

Compatibility of scalar multiplication with field multiplication a(bv) = (ab)v

Identity element of scalar multiplication 1v = v, where 1 denotes the multiplicative identity in F.

Distributivity of scalar multiplication with respect to vector

addition a(u + v) = au + av

Distributivity of scalar multiplication with respect to field

addition (a + b)v = av + bv

λn−λn−1−λn−2=0

λ2−λ−1=0

λ is the common ration of this geometry series. So far, we find what the characteristic equation actually is!

So intrinsically, characteristic equations is used to determine a well-proper vector as bases of V.

5. Now we find the two geometric series (because this equation has two roots) as bases, so we can represent all sequences in V with format ai+bj, where a,b are coordinate of this sequence,i and j are used to denote two bases we found.How to find the coordinates? Well, we still have two initial conditions.

6. 𝐹𝑛=𝑎1+√52𝑛+𝑏1−√52𝑛, we know 𝐹0=0,𝐹1=1,so a=b=1√5

So

7. Similarly, if we consider all smooth function consist V, the bases we will choose are exponential function.

WHAT IF THERE ARE MULTIPLE ROOTS OF CHARACTERISTIC EQUATIONS?

1. Well ,what we should do is to find a independent well-known basis as another vector. Eg. In vector space of second-order linear recurrence sequence. If the root λ is a multiple root for characteristic equation, geometric series with common ratio λ is one basis. The other one is a series with general formula an=n λ 𝑛.

2. Obviously , we can prove it is true. But what is the motivation to consider this weird series?.

3. In fact , we can rewrite

an=uan−1+van−2

to

(𝑎𝑛𝑎𝑛−1)=(uv10)(an−1an−2)

Further more

(𝑎𝑛𝑎𝑛−1)=(uv10)n(a1a0)

So now the question is , how to calculate (uv10)n?

Easy to notice that (PA𝑃−1)𝑛=P𝐴𝑛𝑃−1, and diagonal matrix is easy to find the indices of n.

(a00b)n =(𝑎𝑛00𝑏𝑛)

If we can find a method to make (uv10)=PA𝑃−1 ,we can easily find (uv10)n

To diagonalize a matrix, we should find its eigenvalue. All elements on diagonal in A are eigenvalue, while P is the union of eigenvector with corresponding position ,if the characteristic equation det(M-λI)=0 has no multiple root.(by the way, the equation here is actually the same to what i mentioned above. This explanation is more intrinsic)

BUT AGAIN,WHAT IF THERE ARE MULTIPLE ROOTS OF CHARACTERISTIC EQUATIONS? 4. Fortunately, In linear algebra, a Jordan normal form, also known as a Jordan canonical form or JCF is an upper triangular matrix of a particular form called a Jordan matrix representing a linear operator on a finite-dimensional vector space with respect to some basis. Such a matrix has each non-zero off-diagonal entry equal to 1, immediately above the main diagonal (on the superdiagonal), and with identical diagonal entries to the left and below them.

An n × n matrix A is diagonalizable if and only if the sum of the dimensions of the eigenspaces is n. Or, equivalently, if and only if A has n linearly independent eigenvectors. Not all matrices are diagonalizable; matrices that are not diagonalizable are called defective matrices. Consider the following matrix:

Including multiplicity, the eigenvalues of A are λ = 1, 2, 4, 4. The dimension of the eigenspace corresponding to the eigenvalue 4 is 1 (and not 2), so A is not diagonalizable. However, there is an invertible matrix P such that A=PJ𝑃−1, where

And luckily , we have :

Now, we can find any indices of any matrix ,since we can let every matrix A ,A=PJ𝑃−1according to fundamental algebra theorem.

5. an example to summarize above .

6. Notice here, we naturally find that an=n λ 𝑛 is also a independent basis.

In fact, if the number of one multiple roots is k. an=ni λ 𝑛, 0≤i≤k, i is an integer , are

independent bases.

WHAT IF THE QUESTION IS NON-HOMOGENEOUS?

1. In linear algebra, we always introduce systems of linear equations first then matrix and vector space.

{𝑎11𝑥1+𝑎12𝑥2+⋯…+𝑎1𝑛𝑥𝑛=𝑏1𝑎21𝑥1+𝑎22𝑥2+⋯…+𝑎2𝑛𝑥𝑛=𝑏2…………𝑎𝑛1𝑥1+𝑎𝑛2𝑥2+⋯…+𝑎𝑛𝑛𝑥𝑛=𝑏𝑛

We find what matters is the coefficient of each variable,so we consider each row is a vector, and the union of n vectors is a coefficient matrix A,so Ax=B,x is vectors we try to find. When B=0, we call it homogeneous.

2. Since normally A is a n*n matrix, if the det(A)≠0,the rank(A) is n,which means the system has and only has one root. If the det(A)=0, we can find the number,k, of dependent vectors in matrix and rank(A)=n-k. The dimension of subspace of general solution for Ax=0 is k.

3. Moreover, if Ax=B,is non-homogeneous, we firstly try to find a particular solution x’. The solution of Ax=B is 𝑥0+𝑥′,where 𝑥0 is the complementary solution.

It is to prove : because A(𝑥0+x’)=A𝑥0+Ax’=0+B=B,so 𝑥0+x’ is also a solution if x’ is a particular solution.

4. If we consider this idea more intrinsically, we will find a matrix is a what we used to represent an operator on a vector space. So differentiation is an operator on vector space of smooth functions, which is ,unfortunately, an infinite space, meaning we can’t discuss rank or determinant . But that doesn’t matter, we just need to use the conclusion of structure of solutions.

𝑑2𝑦𝑑𝑥2+𝑢𝑑𝑦𝑑𝑥+ vy = f(x)

(𝑑2𝑑𝑥2+𝑢𝑑𝑑𝑥+𝑣)y=f(x)

Ay=B

So i explained why the non-homogeneous linear questions have solution with structure of the sum of particular solution and complementary one. So does linear recurrence relations.

So far, we finally explain thoroughly the method we learned in A-level from linear algebra, which make we understand the motivation of the method and the theory behind it.