◀ ▲ ▶Branches / Combinatorics / Proposition: Recursively Defined Arithmetic Functions, Recursion

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 1. 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.$

Table of Contents

Proofs: 1

Mentioned in:

Definitions: 1
Propositions: 2

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Aigner, Martin: "Diskrete Mathematik", vieweg studium, 1993