Recurrence relations

Solving recurrence relations

A recurrence defines each term from earlier ones. First order: $u_{n+1}=ku_n+c$ has solution $Ak^n+$ constant. Second order: $u_{n+2}+pu_{n+1}+qu_n=0$ is solved with the auxiliary equation $r^2+pr+q=0$, exactly like differential equations but with powers instead of exponentials.