Recurrence Relation Proofs

Intro to Proofs · Axiom Academy

LESSON Recurrence Relation Proofs From a recursive rule to a closed formula — find it with the characteristic equation, then prove it right with induction. A recurrence relation defines each term from earlier terms. Our running example for the whole lesson: Two seed values, then each term from the previous two Seeds a_0 = 1 and a_1 = 2 . Then a_2 = 5(2) - 6(1) = 4 , a_3 = 5(4) - 6(2) = 8 , a_4 = 16 , a_5 = 32 . To reach a_ 10 you must compute every term in between first. 2. The Characteristic Equation Method For a linear homogeneous recurrence with constant coefficients , a single algebraic trick produces the closed form. Guess that solutions look like a geometric sequence, a_n = r^n , and see what r must be. Guess a solution of the form a_n = r^n . Substitute: r^n = c_1 r^ n-1 + c_2 r^ n-2 . Divide by r^ n-2 to get the characteristic equation : r^2 = c_1 r + c_2 . Solve for the roots r_1 and r_2 . Let's carry the running example all the way to a closed form. The characteristic equation is a quadratic — solving it means finding where its parabola crosses the r -axis . r^2 = 5r - 6 , i.e. r^2 - 5r + 6 = 0 . Before the full proof, do a quick sanity check: does a_n = 2^n actually satisfy the recurrence? Substitute it into the right-hand side and watch it collapse back to the left.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.