# How do I define a function that uses a recurrence relation? [duplicate]

This question already has an answer here:

I know how to define functions other than the ones that use a recurrence relation to calculate the $$n$$-th term of a sequence. How would such a function be constructed?

## marked as duplicate by Daniel Lichtblau, m_goldberg, J. M. is away♦Oct 9 '18 at 15:47

• The title and the text contradict each other. Anyways, RSolve and RecurrenceTable might be of interest. Have also a look at Nest and Fold. – Henrik Schumacher Oct 9 '18 at 13:35
• The first thing you should is search on "recurrence" in the Documentation Center. You also might search on "recursion" on this site. – m_goldberg Oct 9 '18 at 13:39
• You can use Once if you just want to calculate the nth term without repeating previously executed steps. – Gladaed Oct 9 '18 at 13:51
• @user60620: I just want to translate your title as: there is a function f(x,y) where x or y is a recurrence relation. This means that f(x,y) is a nested function, including the recurrence relation. The degree of recurrence should be known. If this clarification reflects what you have, then I can give a simple example. – Tugrul Temel Oct 9 '18 at 13:59
• This question has already been dealt with a number of times. Here are two previous questions which have answers that might be of interest to you: mathematica.stackexchange.com/q/61050/3066 and mathematica.stackexchange.com/q/21746/3066 – m_goldberg Oct 9 '18 at 15:22

An example:

Table[Evaluate[a[n] /. RSolve[{a[n + 1] - 2 a[n] == 1, a[0] == 1}, a[n], n][[1]]], {n, 0, 10}]
(* {1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047} *)


A construct a function:

a[n + 1] - 2 a[n] == 1 -> a[n + 1] == 1 + 2 a[n] -> a[n] == 1 + 2 a[n - 1]


and then:

a[0] = 1;
a[n_] := a[n] = 1 + 2 a[n - 1]
Table[a[n], {n, 0, 10}]
(* {1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047} *)