Examples for

Recurrences

Recurrences, or recurrence relations, are equations that define sequences of values using recursion and initial values. Recurrences can be linear or non-linear, homogeneous or non-homogeneous, and first order or higher order. Wolfram|Alpha can solve various kinds of recurrences, find asymptotic bounds and find recurrence relations satisfied by given sequences. Some methods used for computing asymptotic bounds are the master theorem and the Akra–Bazzi method.

Solving Recurrences

Find closed-form solutions for recurrence relations and difference equations.

Solve a recurrence:

g(n+1)=n^2+g(n)

Specify initial values:

g(0)=1, g(n+1)=n^2+g(n)
f(n)=f(n-1)+f(n-2), f(1)=1, f(2)=2

Solve a q-difference equation:

a(q n)=n a(n)

Finding Recurrences

Deduce recurrence relations to model sequences of numbers or functions.

Find a recurrence satisfied by a given sequence:

fibonacci(n) recurrence

Find a recurrence satisfied by a sequence of functions:

recurrences Laguerre polynomials

Asymptotic Bounds

Find asymptotic bounds for recurrences that involve scaling transformations on the index, such as those that arise in the analysis of divide-and-conquer algorithms.

Find an asymptotic bound for a recurrence equation:

T[n]==T[n/2]+1

Use floor and ceiling to round the index:

f(n)=f(floor(n/2))+f(ceiling(n/2))+n

Compute asymptotic bounds even when a recurrence cannot be solved exactly:

a[n] = n^2 + n^5 + Log[n] + 18 a[n/5] + 13 a[n/3]
f_n = logn + 18 f_(n/5) + 13 f_(n/25)
r(k) = k^2 + log(k) + 49 r(k/6) + 29 r(k/3)

RELATED EXAMPLES

  • Computational Complexity
  • Differential Equations
  • Sequences