استقرای ساختاری
مثال‌ها > شجره نامه باستان، نشان دادن 31 نفر در 5 نسل

شجره نامه یک ساختار داده شناخته شده‌است که پدر و مادر، پدربزرگ و مادربزرگ، و اجداد یک فرد را تا آنجا که شناخته شده باشند نشان می دهد و به صورت بازگشتی تعریف می‌شود:
در ساده‌ترین حالت، یک شجره نامه فقط یک نفر را نشان می دهد (اگر چیزی در مورد پدر و مادر آن شخص مشخص نباشد).
متناوباً، شجره نامه یک نفر را، که توسط شاخه به دو زیر درخت پدر و مادر خود متصل شده است، نشان می دهد(با استفاده از فرضی ساده که اگر :یکی از آن‌ها شناخته شده باشد، پس هر دو شناخته شده اند).
به عنوان مثال، ویژگی " یک شجره نامه که بیش از g نسل را گسترش می دهد حداکثر 2g-1 نفر را نشان می دهد" را می‌توان با استقرای ساختاری ثابت کرد که به شرح زیر است:
در ساده‌ترین حالت، درخت فقط یک نفر را و از این رو یک نسل را نشان می‌دهد. تا زمانی که 1 ≤ 21 - 1 ویژگی مذکور برای چنین درختی درست است.
متناوباً، درخت، درختان یک نفر و والدینش را نشان می‌دهد. از آن جا که هر یک از والدین یک زیرساختار از ساختار درخت هستند، می‌توان صحیح بودن ویژگی مذکور را اثبات شده فرض نمود. که با عنوان فرضیه استقرایی نیز شناخته می‌شود.
پس می‌توان فرض کرد، p ≤ 2g – 1 و q ≤ 2h – 1، که در آن g و h نشان دهنده تعداد نسل‌هایی است که زیردرخت‌های پدر و مادر به ترتیب گسترش می دهند، و p و q نشان دهنده تعداد افرادی است که آن‌ها نشان می دهند.
در صورتی که g ≤ h، کل درخت، بیش از 1 + hنسل گسترش می یابد و p + q + 1 نفر را نشان می‌دهد. و
در صورتی که h ≤ g، کل درخت، بیش از 1 + g نسل گسترش می یابد و همینطور p + q + 1 ≤ 2(1 + g) - 1 نفر را با استدلالی مشابه نشان می‌دهد. یعنی کل درخت در این مورد نیز ویژگی مذکور را برآورده می سازد.
به عنوان مثالی رسمی تر، ویژگی مربوط به لیست‌های زیر را در نظر بگیرید:
[length (L ++ M) = length L + length M          [EQ
در اینجا ++ نشان دهنده عمل الحاق لیست هاست وL و M لیست می‌باشند.
به منظور اثبات این ویژگی، ما تعاریف طول(length) و عمل الحاق(++) را نیاز داریم. قرار دهید (h : t) که لیستی را که سر (عنصر اول) آن h و دم (فهرست عناصر باقی مانده) آن T است نشان می دهد، و اجازه دهید [] نشان دهنده ی لیست خالی باشد. تعاریف طول(length) و عمل الحاق(++) عبارتند از:
[length []     = 0                  [LEN1
   [length (h:t)  = 1 + length t       [LEN2
   
   [list = list               [APP1 ++    []
   [h:t) ++ list = h : (t ++ list)    [APP2)
گزاره (P(l ما برابراست با EQ برای همه لیست‌های M درست است اگر L برابر l باشد. می خواهیم نشان می دهیم که (P(l برای همه لیست‌های l درست است. ما این کار را با استقرای ساختاری بر لیست‌ها ثابت خواهیم کرد.
ابتدا ثابت می‌کنیم که ([])P درست است. که در واقع برابر است با، EQ درست است برای همه لیستهای M زمانی که L برابر لیست خالی [] است. EQ را به صورت زیردر نظر بگیرید:
(length (L ++ M)  = length ([] ++ M
          (length M               (by APP1 =
                              0 + length M = 
          (length [] + length M   (by LEN1 =
                      length L  + length M =
بنابراین این بخش از قضیه ثابت شد. EQ برای همه Mها درست است، هنگامی که L برابر [] است، چرا که سمت چپ و سمت راست برابرند.
سپس، هر لیست مخالف تهی I را در نظر بگیرید. از آنجا که l مخالف تهی است، پس یک سر، x ، و یک لیست دم، xs ، دارد. بنابراین ما می‌توانیم آن را به عنوان (x: xs) بیان کنیم. فرض استقرا این است که EQ برای تمام مقادیر M زمانی است که L برابر xs است درست باشد:
(length (xs ++ M) = length xs + length M    (hypothesis
میخواهیم نشان دهیم که در صورت برقراری این شرایط EQ برای تمام مقادیر M هنگامی که (L = I = (x: xs درست است.همانند قبل ادامه می دهیم:
length L  + length M      = length (x:xs) + length M
                   1 + length xs + length M =      
                       1 + (length (xs ++ M = 
                       (length (x: (xs ++ M =
                       (length ((x:xs) ++ M = 
                            (length (L ++ M =
بنابراین، ما بوسیله ی استقرای ساختاری، به دست آوردیم که (P(L برای همه لیست‌های L درست است.