A Linear Recurrence Relation is one of the form
u0 is a constant, and
un+1 = a un + b
On this page we'll find a closed form for this type of recurrence relation.
Linear Recurrence Relation
A linear recurrence relation of the form un+1=aun+b has
the closed form
un = (u0+b/(a-1))an - b/(a-1)
Here's how to derive it:
u1=au0+b
u2=au1+b = a(au0+b)+b = u0a2
+ ba + b
u3=au2+b = a(u0a2+ba+b)+b = u0a3+ba2+ba+b
u4=au3+b = a(u0a3+ba2+ba+b)+b
= u0a4+ba3+ba2+ba+b
...
un = u0an+ban-1+...+ba2+ba+b
To simplify the right-hand-side, note that
an-1+an-2+...+a+1 = (an-1)/(a-1)
So,
un = u0an + b(an-1)/(a-1)
un = u0an + ban/(a-1) - b/(a-1)
un = (u0+b/(a-1))an-b/(a-1)
Related
pages in this website
Fibonacci Numbers --
whose successive ratios approach big phi
Recurrence Relation Puzzle 1,
having to do with Fibonacci Numbers
Increasing Function Puzzle 1
-- Find the closed form of this function defined as a recurrence relation
