example of closed form

Consider the recurrence given by x0=7 and xn=2xn-1. Then it can be proved by inductionMathworldPlanetmath that xn=2n7.

The expression xn=2n7 is a closed form expression the recurrence given, since it depends exclusively on n , whereas the recurrence depends on n and xn-1 (the previous value).

Now consider Fibonacci’s recurrence:


It is not a closed formula, since if we wanted to compute f10 we would need to know f9, f8 (and for knowing them, the previous terms too). However, such recurrence has a closed formula, known as Binet formula:


Binet formula is closed, since if we wanted to compute fn we only need to substitute n on the previous formulaMathworldPlanetmathPlanetmath, and no additional information is required.

Title example of closed form
Canonical name ExampleOfClosedForm
Date of creation 2013-03-22 15:03:07
Last modified on 2013-03-22 15:03:07
Owner drini (3)
Last modified by drini (3)
Numerical id 4
Author drini (3)
Entry type Example
Classification msc 11B99