Math 2.0

Number theory Concept

Recursively defined sequence

Builds on Sequence

Summary

A recursively defined sequence is a sequence given by its first terms and a rule that computes each later term from the terms before it. A typical form is a0=ca_0 = c and an+1=f(n,an)a_{n+1} = f(n, a_n) for a given value cc and a given function ff. The recursion theorem shows that exactly one sequence satisfies such a rule.

Remarks

The factorials satisfy 0!=10! = 1 and (n+1)!=(n+1)⋅n!(n+1)! = (n+1) \cdot n!. The Fibonacci numbers satisfy F0=0F_0 = 0, F1=1F_1 = 1 and Fn+2=Fn+1+FnF_{n+2} = F_{n+1} + F_n. Here each term needs the two terms before it. In analysis, the sequence a0=1a_0 = 1, an+1=12(an+2/an)a_{n+1} = \frac{1}{2}(a_n + 2/a_n) converges to 2\sqrt{2}. It is Newton's method for x2−2x^2 - 2. The rule that links the terms is a recurrence relation.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph
Sequence, definition, no evidence levelSequencedefinitionRecursively defined sequence, concept, no evidence levelRecursively defined s…concept
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Sequence definition
  2. Recursively defined sequence concept

Further reading

  1. Web https://en.wikipedia.org/wiki/Recurrence_relation, Definition
  2. Web https://en.wikipedia.org/wiki/Sequence, Defining a sequence by recursion
About this page
Tag0ZPV68RN1X
URIm2://0ZPV68RN1X
Kindconcept
WritingW0 stub
MSC11B37
UsesSequence

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.