Recurrences Reference

Discrete Math · Axiom Academy

FORMULA SHEET Recurrence Relations Reference Solution methods, Master Theorem, common sequences, and generating functions CHARACTERISTIC EQUATION METHOD Use initial values to solve for constants Find particular solution based on forcing function type, then add to homogeneous solution MASTER THEOREM (DIVIDE AND CONQUER) COMMON SEQUENCES AND THEIR RECURRENCES Sequence encoded as power series coefficients GENERATING FUNCTION OPERATIONS IMPORTANT GENERATING FUNCTIONS PARTICULAR SOLUTIONS (Non-Homogeneous) Expand terms and look for patterns Repeatedly substitute until pattern emerges Successive cancellation of terms USEFUL IDENTITIES FOR SOLVING RECURRENCES

This is the written version of the interactive lesson above. See the full Discrete Math course.