Differensekvation
Differensekvationer (även kallade rekursionsekvationer, ibland rekurrensrelationer efter den engelska benämningen) är den diskreta matematikens motsvarighet till analysens differentialekvationer. Givet en rekursionsformel eftersöks de talföljder som satisfierar densamma. Ofta ges ett antal randvillkor vilka ytterligare begränsar lösningsmängden.
Differensekvationer kan lösa många annars svårlösliga problem, exempelvis hur många flyttningar som måste genomföras i spelet Tornen i Hanoi. En känd differensekvation är den som beskriver Fibonaccitalen.
Linjära differensekvationer med konstanta koefficienter
redigeraEn linjär differensekvation av p:te ordningen med konstanta koefficienter kan skrivas på formen
Fn=a1Fn-1+ ... +apFn-p.
Den löses på ett sätt som nära överensstämmer med hur en linjär differentialekvation med konstanta koefficienter löses. En karakteristisk ekvation erhålles således och den slutliga lösningen till differensekvationen är på formen Fn=C1b1n+...+Cpbpn.
Fibonaccis serie
redigeraFöljande differensekvation beskriver Fibonaccitalen:
Fn=Fn-1+Fn-2 med F1=F2=1.
Att finna en lösning till en differensekvation är att hitta en explicit formel för talföljden. I detta fall är den explicita formeln
där
Detta är således en icke-rekursiv lösning.