Recursion

Recursion is defining something in terms of a previous term, function, etc. For example, the famous Fibonacci sequence is defined recursively. If we let be the nth term, the sequence is: , and so on. A recursive definition is: . That is a symbolic way to say "The next term is the sum of the two previous terms".

Examples

• A combinatorical use of recursion: AIME 2006I/11
• Use of recursion to compute an explicit formula: AIME 2006I/13

See also

• Combinatorics
• Sequence
• Induction