 Welcome guest
You're not logged in.
289 users online, thereof 0 logged in

## Proposition: Recursively Defined Arithmetic Functions, Recursion

An arithmetic function $f:\mathbb N\to\mathbb C$ can be defined by specifying

1. the initial values of $f(m)$ for all $m\le N$ and some natural number $N\in\mathbb N,$ and
2. the recursion formula $f(n)=\mathcal R(f(m)\mid m < n)$ for all $n > N.$

### Examples

• factorial function $f:\mathbb N\to\mathbb N:$
• $N:=0,$
• initial value $f(0):=1,$
• recursion formula $f(n):=n\cdot f(n-1).$
• Fibonacci function $f:\mathbb N\to\mathbb N:$
• $N:=2,$
• initial values $f(0):=0, f(1):=1, f(2):=1,$
• recursion formula $f(n):=f(n-1)+f(n+2).$
• Mandelbrot function $f:\mathbb N\to\mathbb C:$
• $N:=0,$
• initial value $f(0):=0,$
• recursion formula $f(n):=f(n-1)^2+c$ for some complex number $c\in\mathbb C.$

## 1.Proof: (related to "Recursively Defined Arithmetic Functions, Recursion")

### Bibliography (further reading)

 Aigner, Martin: “Diskrete Mathematik”, vieweg studium, 1993