構造的帰納法
家系図は次のように再帰的に定義される、よく知られた木構造である。
最も簡単なケースでは、家系図はたった1人だけを記す。(その人の両親が知られていない場合。)
あるいは、1人と、その両親の家系図2つへの枝からなる。(証明を簡単にするため、一方の親が知られていたら、両方とも知られていることにしている。)
例として、性質「g 世代にわたる家系図は、多くとも 2-1 人だけを記している。」を、構造的帰納法によって次のように証明する。
単純なケースでは、家系図はちょうど1人だけを記す。そのため g = 1 である。1 ≦ 2 - 1 であるから、前述の性質を満たしている。
あるいは、家系図は1人とその両親の家系図からなる。親の家系図はいずれも全体の家系図の部分構造だから、それらは前述の性質を満たしていると仮定できる。(これを帰納法の仮定(induction hypothesis)という。) すなわち、親の家系図に記される世代の数をそれぞれ g, h で表し、親の家系図に記される人数をそれぞれ p, q で表すと、p ≦ 2-1 と q ≦ 2-1 が成り立つ、と仮定する。 g ≦ h のとき、全体の家系図は (h + 1) 世代にわたり、記されているのは p + q + 1 人である。p + q + 1 ≦ (2 - 1) + (2 - 1) + 1 ≦ (2 - 1) + (2 - 1) + 1 = (2 - 1) + 1。ゆえに、全体の家系図が性質を満たしていることが分かる。 h ≦ g のときも同様。
したがって、すべての家系図が上記の性質を持つ。