# example of closed form

Consider the recurrence given by
${x}_{0}=7$ and ${x}_{n}=2{x}_{n-1}$. Then it can be proved by induction^{} that
${x}_{n}={2}^{n}\cdot 7$.

The expression ${x}_{n}={2}^{n}\cdot 7$ is a closed form expression the recurrence given, since it depends exclusively on $n$ , whereas the recurrence depends on $n$ and ${x}_{n-1}$ (the previous value).

Now consider Fibonacci’s recurrence:

$${f}_{n}={f}_{n-1}+{f}_{n-2},{f}_{0}=1.$$ |

It is not a closed formula, since if we wanted to compute ${f}_{10}$ we would need to know ${f}_{9}$, ${f}_{8}$ (and for knowing them, the previous terms too). However, such recurrence has a closed formula, known as Binet formula:

$${f}_{n}=\frac{{\left(\frac{1+\sqrt{5}}{2}\right)}^{n}-{\left(\frac{1-\sqrt{5}}{2}\right)}^{n}}{\sqrt{5}}.$$ |

Binet formula is closed, since if we wanted to compute ${f}_{n}$ we only need to substitute $n$ on the previous formula^{}, 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 |