# An oldest-to-newest order-two recurrence trace

[← Guide index](https://ocme.evemisslab.com/en/derivations/) · [Original MKO](https://ocme.evemisslab.com/en/mko/mko-recurrence-relation/)

This is an owner-adopted natural-language teaching guide. Finite/arithmetic checks are not universal proofs; no Lean was run, and review scope is recorded per revision. Original source status labels are retained as historical data. Formulas retain exact TeX; no new semantic AST is invented.

derivation-mko-recurrence-relation-01 · ocme-new142-reader-adoption-20261021



## Goal and scope

Align states, coefficients and all initial values, generate a5 and explain uniqueness.

A finite exact integer trace, without guessing a closed form.





## Givens and symbols


- work


- G1 — Order r=2, initial_values=(a0,a1)=(1,3), coefficients=(2,1), constant=1; for all n≥2 use a_n=1+2a_(n-2)+a_(n-1).


- A_n — latest-two-term state
- F — shift-and-append update





## Rules and sources


- mko_definition · cited — An order-r recurrence needs all r initial values and coefficients aligned oldest to newest. Shift the state left and append the new term. A finite prefix proves no closed form, convergence or asymptotics. · mko-recurrence-relation
- work · prerequisite — Order-r states are ordered oldest to newest; the single-valued integer update is total; induction from all initial values proves uniqueness.





## Main derivation

S01 · impliesBefore

A_1=(a_0,a_1)=(1,3)

After

F(u,v)=(v,1+2u+v)

Conditions: none

Rule: work · Uses: G1, work

Leaf basis: work

Multiply the oldest u by 2 and newest v by 1, then shift left and append.



S02 · impliesBefore

a_2=1+2(1)+3

After

a_2=6,\quad A_2=(3,6)

Conditions: none

Rule: work · Uses: G1, S01, work

Leaf basis: work

The first update retains old newest3 as the first state entry.



S03 · impliesBefore

a_3=1+2(3)+6

After

a_3=13,\quad A_3=(6,13)

Conditions: none

Rule: work · Uses: G1, S02, work

Leaf basis: work

Align A2 correctly to compute the next term.



S04 · impliesBefore

a_4=1+2(6)+13

After

a_4=26,\quad A_4=(13,26)

Conditions: none

Rule: work · Uses: G1, S03, work

Leaf basis: work

Shift again and append26.



S05 · impliesBefore

a_5=1+2(13)+26

After

a_5=53,\quad A_5=(26,53)

Conditions: none

Rule: work · Uses: G1, S04, work

Leaf basis: work

The finite target index 5 has been fully generated.



S06 · impliesBefore

a_0=b_0,\ a_1=b_1\quad\text{and same recurrence}

After

(a_{n-2},a_{n-1})=(b_{n-2},b_{n-1})\implies a_n=b_n

Conditions: none

Rule: work · Uses: G1, S05, work

Leaf basis: work

The same single-valued update sends equal preceding pairs to equal next terms.



S07 · impliesBefore

a_0=b_0=1,\ a_1=b_1=3

After

a_n=b_n\quad\text{for every }n\ge0

Conditions: none

Rule: work · Uses: G1, S06, work

Leaf basis: work

Using the two initial values as base and the preceding implication as step, induction gives sequence uniqueness.



S08 · impliesBefore

a_0=1\text{ only},\quad a_1=t

After

a_2=3+t\text{ depends on }t

Conditions: none

Rule: work · Uses: G1, S07, work

Leaf basis: work

Without the second initial value, different t produce different valid sequences, so uniqueness fails.







## Substeps and lemmas

No substeps in this guide.





## Reverse audits


- S08 · premise_audit · G1, S07, work — Completing a finite trace asserts no convergence or asymptotics.
- S07 · premise_audit · G1, S06, work — Uniqueness does not prove a closed form or growth rate.
- S06 · premise_audit · G1, S05, work — The induction base requires both initial values.
- S05 · premise_audit · G1, S04, work — Every intermediate value is an explicitly small integer.
- S04 · premise_audit · G1, S03, work — The constant 1 appears at every update.
- S03 · premise_audit · G1, S02, work — The coefficient 2 multiplies3, not 6.
- S02 · premise_audit · G1, S01, work — The state is not merely the new scalar6.
- S01 · premise_audit · G1, work — Do not reverse coefficients to u+2v.





## Error controls and negative controls

Coefficient alignmentPair(2,1) with a_(n-2),a_(n-1).

State widthKeep two terms in every state, shifting before appending.


- a2=1+1+2 times 3=8. → reject — The oldest term gets coefficient 2, yielding6.
- a0=1 alone gives uniqueness. → reject — a1=t leaves a2=3+t variable.
- Six increasing terms prove divergence. → reject — A finite prefix cannot prove an infinite-tail property.





## Result and limitations

The prefix is 1,3,6,13,26,53; two initial values and the total rule determine a unique sequence.







## Verification and source binding

2 declared checks for this guide; only the listed expressions are covered.


- source commit: b1b2f1dcf8c50d67a93fe52d95f8eef7b3abba9f
- adopted source SHA-256: 124f407c6762352d6b2a2e969d2d845466e4482a03a8f31e13b95650c4a212a5
- original source SHA-256: 22806b93c67d3eddec49366fb95886552a6c5b9b138df147ef955ed07c293e53
- Lean: NOT_RUN · independent AI: SCOPED_LEAD_AND_BILINGUAL_CONTEXT_REVIEW

[Same-source full JSON (formulas, ASTs, controls and revision log)](https://ocme.evemisslab.com/data/derivations/coverage-20261021/guides/derivation-mko-recurrence-relation-01.json)