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

[redigera | redigera wikitext]

En 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

[redigera | redigera wikitext]

Fö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.