再帰
有限分割規則は再帰の幾何学的形式で、これはフラクタル模様を作図するのに使用される。分割規則は、有限に多くのラベルでラベル付けされた多角形の集まりを起点として、各多角形は最初の多角形ラベルにのみ依存する方法で、より小さなラベル付き多角形に分割される。この工程は繰り返し行うことができる。カントール集合を作るための標準的な「3等分の中央部を除去する」技法が、分割規則の例である。
2つの関数 F : N → X {\displaystyle F:\mathbb {N} \to X} と G : N → X {\displaystyle G:\mathbb {N} \to X} を採ると:
F ( 0 ) = a {\displaystyle F(0)=a}
G ( 0 ) = a {\displaystyle G(0)=a}
F ( n + 1 ) = f ( F ( n ) ) {\displaystyle F(n+1)=f(F(n))}
G ( n + 1 ) = f ( G ( n ) ) {\displaystyle G(n+1)=f(G(n))}
ここでaはXの要素である。
すべての自然数nについてF(n) = G(n) であることは数学的帰納法によって証明できる。
基底段階: F(0) = a = G(0) だからn = 0に対して等式が成り立つ。
帰納段階: ある k ∈ N {\displaystyle k\in \mathbb {N} } .についてF(k) = G(k)と仮定すると、F(k + 1) = f(F(k)) = f(G(k)) = G(k + 1)である。 したがってF(k) = G(k) は F(k + 1) = G(k + 1)を含んでいる。
帰納法により、全ての n ∈ N {\displaystyle n\in \mathbb {N} } についてF(n) = G(n)である。