Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Sequences and Series > Recurrence Relations > Linear Recurrence Relation

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

 


The webmaster and author of this Math Help site is Graeme McRae.