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

En linjär differensekvation av p:te ordningen med konstanta koefficienter kan skrivas på formen

F_n=a₁F_n-1+ ... +a_pF_n-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 F_n=C₁b₁ⁿ+...+C_pb_pⁿ.

Fibonaccis serie

Följande differensekvation beskriver Fibonaccitalen:

F_n=F_n-1+F_n-2 med F₁=F₂=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

$F\left(n\right)={{\Phi ^{n}-(1-\Phi )^{n}} \over {\sqrt {5}}},$

där

$\Phi ={{1+{\sqrt {5}}} \over {2}}.$

Detta är således en icke-rekursiv lösning.