روابط بازگشتی
Recurrence Relations
حل روابط بازگشتی خطی با معادلهٔ مشخصه و توابع مولد.
ریاضیات گسسته کنکور ارشد علوم کامپیوتر
کارتها · 5
Turn a constant-coefficient recurrence into a polynomial; its roots (and their multiplicity) give the closed form.
Guess a particular solution shaped like the forcing term (polynomial, exponential, or their product), match coefficients to solve for it, and multiply by a power of n whenever the guess collides with a root of the homogeneous part.
When a characteristic root r is repeated with multiplicity m , it contributes (c_0 + c_1 n + … + c_(m-1) n^(m-1)) r^n to the general solution, not just c r^n .
A linear recurrence reduced mod m depends only on a finite state of past residues, so its residue sequence is eventually periodic — find the period, then answer any far-out term with n mod p .
When each iteration replaces every segment by k copies scaled by factor r, the total length is multiplied by kr each step — so it grows geometrically as (kr)^n.