A Linear Recurrence Relation is one of the form

u₀ is a constant, and
u_n+1 = a u_n + 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 u_n+1=au_n+b has the closed form

u_n = (u₀+b/(a-1))aⁿ - b/(a-1)

Here's how to derive it:

u₁=au₀+b

u₂=au₁+b = a(au₀+b)+b = u₀a² + ba + b

u₃=au₂+b = a(u₀a²+ba+b)+b = u₀a³+ba²+ba+b

u₄=au₃+b = a(u₀a³+ba²+ba+b)+b = u₀a⁴+ba³+ba²+ba+b

...

u_n = u₀aⁿ+ba^n-1+...+ba²+ba+b

To simplify the right-hand-side, note that

a^n-1+a^n-2+...+a+1 = (aⁿ-1)/(a-1)

So,

u_n = u₀aⁿ + b(aⁿ-1)/(a-1)

u_n = u₀aⁿ + baⁿ/(a-1) - b/(a-1)

u_n = (u₀+b/(a-1))aⁿ-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.