0% Complete
0/19 Steps

In Progress

Linear difference equations

Definition
linear difference equation is a recurrence relation of the form $y_{t+n}=a_1y_{t+n-1}+a_2y_{t+n-2}+\cdots +a_ny_t+b$. If $b=0$, then it is called homogeneous. In this article, we shall also assume $t=0$ for convenience. The name “difference equation” is a nod to the fact that it is analogous to a differential equation if we take finite differences instead of taking limits. (Note that, $\frac{dy}{dx}=\lim_{h\to 0}\frac{y(x+h)-y(x)}{h}=\lim_{\Delta x\to 0}\frac{\Delta y}{\Delta x}$.) In what follows, we shall illustrate a common method to explicitly solve such equations.

The solution space
Note that, if two sequences $z_n$ and $w_n$ are solutions to the given equation (in the homogeneous case), then $az_n+bw_n$ is also a solution for any two constants $a,b$. In such cases, the set of all solutions is said to possess a linear structure. It means that the solutions can be thought of as vectors in an abstract space (more on this later). If this space is simply $\mathbb{R}^2$ or $\mathbb{R}^3$, then we can use our knowledge of vectors in these spaces to find all solutions in terms of a few special ones.

A useful example
Consider the equation $y_n=py_{n-1}+qy_{n-2}$. Note that, given $y_0$ and $y_1$, $y_n$ is determined for all $n\ge 2$. Thus, there exists a one-to-one correspondence between the set of all solutions (let us call it $\Gamma$) and the set of all $(y_0,y_1)$ (the latter is just $\mathbb{R}^2$). Hence, $\Gamma$ is nothing but $\mathbb{R}^2$ (in linear algebra, this correspondence is called a linear isomorphism). Note that, given two non-colinear vectors in the plane, any third vector can be written as a linear combination of the first two (please check!). Thus, given the solutions corresponding to two such vectors, any other solution can be written as a linear combination of them.
The method
Let us look for solutions of the form $y_n=\lambda^n$. Plugging into the equation, we get $\lambda^2-p\lambda-q=0$ (this is called the characteristic equation of the recurrence). Solving, we get two values $\lambda_+$ and $\lambda_-$. If they are different, then the corresponding vectors in $\mathbb{R}^2$ are not colinear (check!). Hence, given any solution $x_n$ there exist $a,b$ such that $x_n=a\lambda_+^n+b\lambda_-^n$. If the roots are the same, then the $x_n$ maybe written in the form $(a+bn)\lambda^n$ (why?)

The above method generalises to difference equations with solution spaces of dimension higher than 2 if the roots of the characteristic equation are all distinct. However, the trick used to deal with coincident roots in the example does not generalise immediately to higher dimensions.

The non-homogeneous case can be transformed into the homogeneous case by making a linear change of variables. See more on this here.

Solving a congruence

Understand the problemProve that the number of ordered triples   in the set of residues of $latex p$ such that , where  and  is prime is . Brazilian Olympiad Revenge 2010 Number Theory Medium Elementary Number Theory by David Burton Start with hintsDo you really need...

Inequality involving sides of a triangle

Understand the problemLet  be the lengths of sides of a (possibly degenerate) triangle. Prove the inequalityLet  be the lengths of sides of a triangle. Prove the inequalityCaucasus Mathematical Olympiad Inequalities Easy An Excursion in Mathematics Start with hintsDo...

Spanning matrix space by niltopent matrices: TIFR 2018 Part A, Problem 15

This problem is a cute and simple application of spanning matrix space by niltopent matrices in the linear algebra section. It appeared in TIFR GS 2018.

Calculating eigenvalues through geometry:TIFR 2018 Part A, Problem 14

This problem is a cute and simple application of calculating eigenvalues through geometry in the linear algebra section. It appeared in TIFR GS 2018.

Direct product of groups: TIFR 2018 Part A, Problem 9

This problem is a cute and simple application of the direct product of groups in the abstract algebra section. It appeared in TIFR GS 2018.

Real Symmetric matrix: TIFR 2018 Part A, Problem 6

This problem is a cute and simple application of the direct product of groups in the abstract algebra section. It appeared in TIFR GS 2018.

Arithmetical Dynamics: Two possible problems

This problem is a cute and simple application of the real symmeric matrices in the linear algebra section. It appeared in TIFR GS 2018.

Arithmetical Dynamics: An intro:

1.1. Existence of (pre)Periodic Points. These are the topics expanding on I.N. Baker’s theorem. Related reading: (1) Silverman Arithmetic of Dynamical Systems: p 165. Bifurcation polynomials. Exercise 4.12 outlines some known properties and open questions (** = open...

Research in Arithmetical Dynamics: Steps

Here I gave some introduction of Arithmetical Dynamics. What is it and why do we study it. Also there is one motivational question upraised.

Class aptent taciti sociosqu ad litora torquent per conubia nostra, per inceptos himenaeos. Sed molestie, velit ut eleifend sollicitudin, neque orci tempor nulla, id sagittis nisi ante nec arcu.

Free Courses

Duis egestas aliquet aliquet. Maecenas erat eros, fringilla et leo eget, viverra pretium nulla. Quisque sed augue tincidunt, posuere dui tempor.