Math 2.0

Difference and functional equations Theorem

Solutions of an advancement operator equation with distinct roots

Builds on Characteristic polynomial of a linear recurrenceSolution of a linear recurrence

Statement

Let AA be the advancement operator on sequences, so that (Af)(n)=f(n+1)(Af)(n) = f(n+1). Let r1,…,rkr_1, \dots, r_k be distinct non-zero constants. Consider the equation (A−r1)(A−r2)⋯(A−rk)f=0(A - r_1)(A - r_2)\cdots(A - r_k) f = 0.

Then every solution ff of this equation can be written as f(n)=c1r1n+c2r2n+⋯+ckrknf(n) = c_1 r_1^n + c_2 r_2^n + \dots + c_k r_k^n for some constants c1,…,ckc_1, \dots, c_k.

Remarks

The polynomial p(A)=(A−r1)⋯(A−rk)p(A) = (A - r_1)\cdots(A - r_k) is the characteristic polynomial of the recurrence, and r1,…,rkr_1, \dots, r_k are its roots. The statement says that the sequences rinr_i^n span all solutions.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph
Recurrence relation, definition, no evidence levelRecurrence relationdefinitionLinear recurrence with constant coefficients, definition, no evidence levelLinear recurrence wit…definitionCharacteristic polynomial of a linear recurrence, definition, no evidence levelCharacteristic polyno…definitionSolution of a linear recurrence, definition, no evidence levelSolution of a linear …definitionSolutions of an advancement operator equation with distinct roots, statement, no evidence levelSolutions of an advan…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Recurrence relation definition
  2. Linear recurrence with constant coefficients definition
  3. Characteristic polynomial of a linear recurrence definition
  4. Solution of a linear recurrence definition
  5. Solutions of an advancement operator equation with distinct roots statement

Further reading

  1. Web https://github.com/mitchkeller/applied-combinatorics/blob/ebd95d6bd59e23c633c65cf560bcb93efa912aae/source/s_recurrence_rigorous.ptx#L103, source/s_recurrence_rigorous.ptx:103
About this page
TagX2YNES3X3K
URIm2://X2YNES3X3K
Kindstatement, theorem
WritingW0 stub
MSC39A06
StatusThis copy of the site has no build data. Run m2 status X2YNES3X3K.
UsesCharacteristic polynomial of a linear recurrence, Solution of a linear recurrence
Changed4 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.