---
tag: DV00798WNX
kind: definition
name: Initial value problem for a recurrence
msc: [39A05]
defines: SSYN7X11MB
uses: [07TZV87Y0T, J00G7MTBFB]
sources:
  - url: https://en.wikipedia.org/wiki/Recurrence_relation
---

## Definition

Let $X$ be a set, let $k \ge 1$ be an integer, and let $f \colon \N \times X^k \to X$ be a function.
Let $c_0, \dots, c_{k-1} \in X$.
The *initial value problem* for the [[recurrence relation|07TZV87Y0T]] of [[order|SNRN446BHC]] $k$ given by $f$, with initial values $c_0, \dots, c_{k-1}$, is the system
$$u_{n+k} = f(n, u_n, \dots, u_{n+k-1}) \quad (n \ge 0), \qquad u_0 = c_0, \ \dots, \ u_{k-1} = c_{k-1}.$$
A *solution* is a sequence $(u_n)_{n \ge 0}$ in $X$ that satisfies all these equations.

## Remarks

Every such problem has exactly one solution.
The terms $u_k, u_{k+1}, \dots$ are computed one after the other from the recurrence, and induction on $n$ shows that no other choice is possible.
Example: $u_{n+2} = u_{n+1} + u_n$ with $u_0 = 0$ and $u_1 = 1$ has the solution $0, 1, 1, 2, 3, 5, \dots$, the Fibonacci numbers.
Non-example: giving only $u_0 = 0$ for this order $2$ recurrence is not an initial value problem in this sense.
Both $0, 0, 0, \dots$ and $0, 1, 1, 2, \dots$ satisfy the recurrence with $u_0 = 0$, so one initial value is too few.
Initial conditions may also be placed at another starting index $n_0$ instead of $0$.