Recursive সংজ্ঞা আর structural induction

১ · নিজের ছোট রূপ দিয়ে সংজ্ঞা — recursive function

বাজারঘরের মেনুতে “ইলেকট্রনিক্স” বিভাগের ভেতরে “মোবাইল”, তার ভেতরে “চার্জার”, তার ভেতরে আবার “দ্রুত চার্জার”। বিভাগের সংজ্ঞা দিতে গেলে স্বাভাবিকভাবে বলি: “একটি বিভাগ হলো একটি নাম আর কয়েকটি পণ্য, সঙ্গে শূন্য বা বেশি বিভাগ।” সংজ্ঞার ভেতরেই সংজ্ঞায়িত শব্দটি এলো। এটি চক্রাকার যুক্তি নয়, কারণ ভেতরের বিভাগগুলো ছোট, আর একসময় পণ্য ছাড়া আর কিছু থাকে না। এই ধরনের সংজ্ঞাকে বলে recursive definition (পুনরাবৃত্তিমূলক সংজ্ঞা)।

তিনটি পরিচিত উদাহরণ:

• Factorial: 0! = 1; n! = n · (n − 1)! যখন n ≥ 1. তাই 4! = 4 · 3! = 4 · 3 · 2! = … = 24.
• Fibonacci: f(0) = 0, f(1) = 1; f(n) = f(n − 1) + f(n − 2) যখন n ≥ 2. এখানে দুটি basis মান লাগে, কারণ নিয়মটি দুই ধাপ পেছনে তাকায়। প্রথম কয়েকটি: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.
• GCD (গরিষ্ঠ সাধারণ গুণনীয়ক): gcd(a, 0) = a; gcd(a, b) = gcd(b, a mod b) যখন b > 0. যেমন gcd(252, 198) = gcd(198, 54) = gcd(54, 36) = gcd(36, 18) = gcd(18, 0) = 18. এই নিয়ম কেন ঠিক, তা পর্ব ২১ “GCD আর Euclid-এর algorithm”-এর বিষয়; এখানে শুধু এর আকারটি দেখুন।

সংজ্ঞা থেকে সূত্র — অনুমান, তারপর প্রমাণ

বাজারঘরের গুদামে প্যাকিংয়ের একটি নিয়ম: n স্তরের একটি চালান সাজাতে প্রথমে n − 1 স্তরের চালান দুবার সাজাতে হয়, আর মাঝে একটি বাড়তি কাজ। কাজের সংখ্যা c(0) = 0, c(n) = 2c(n − 1) + 1 (n ≥ 1). এটি একটি recursion, কিন্তু c(20) জানতে কুড়িবার হিসাব করতে হয়। বন্ধ সূত্র কি আছে? প্রথমে ছোট মান: c(0) = 0, c(1) = 1, c(2) = 3, c(3) = 7, c(4) = 15. প্রতিটি একটি দুইয়ের ঘাতের চেয়ে ১ কম। অনুমান: c(n) = 2ⁿ − 1.

1. Basis: c(0) = 0 = 2⁰ − 1.
2. ধরি কোনো k ≥ 0-এর জন্য c(k) = 2^k − 1 (inductive hypothesis).
3. সংজ্ঞায় c(k + 1) = 2c(k) + 1 = 2(2^k − 1) + 1 = 2^k+1 − 2 + 1 = 2^k+1 − 1. ∎

এটিই এই মডিউলের কাজের ধারা: ছোট ক্ষেত্রে হিসাব, প্যাটার্ন দেখে অনুমান, তারপর induction-এ প্রমাণ। c(20) = 2²⁰ − 1 = 1048575, এক লাইনে। এই recurrence-টি Tower of Hanoi-র চালের সংখ্যাও; recurrence থেকে মডেল বানানো পর্ব ৪৪-এর বিষয়।

Factorial-এ n কমে n − 1 হয়; Fibonacci-তে n − 1 আর n − 2; gcd-তে দ্বিতীয় argument b থেকে a mod b হয়, যা b-এর চেয়ে ছোট। তিন ক্ষেত্রেই কিছু একটা অঋণাত্মক পূর্ণসংখ্যা প্রতিবার কমে। অঋণাত্মক পূর্ণসংখ্যা অসীমবার কমতে পারে না, তাই recursion একসময় basis-এ পৌঁছায়। এই যুক্তির নাম well-ordering principle: ℕ-এর প্রতিটি অশূন্য উপসেটে একটি ক্ষুদ্রতম উপাদান আছে। এর বিস্তারিত আর induction-এর সঙ্গে এর সম্পর্ক পর্ব ১১ “Strong induction আর well-ordering”-এ আছে।

প্রমাণ (uniqueness অংশ, induction দিয়ে): ধরি f আর f′ দুটোই শর্ত মানে। P(n): “f(n) = f′(n)”.

1. Basis: f(0) = c = f′(0), দুটোই প্রথম শর্ত থেকে। তাই P(0) সত্য।
2. ধরি কোনো k ≥ 0-এর জন্য P(k) সত্য, অর্থাৎ f(k) = f′(k) (inductive hypothesis).
3. দ্বিতীয় শর্তে f(k + 1) = g(k + 1, f(k)) আর f′(k + 1) = g(k + 1, f′(k)).
4. ধাপ ২ অনুযায়ী g-এর দুই argument একই, আর g একটি function, তাই দুই মান সমান: P(k + 1) সত্য।
5. Mathematical induction (পর্ব ১০) অনুযায়ী সব n-এর জন্য P(n) সত্য, তাই f = f′. ∎

অস্তিত্বের অংশটিও (এমন f আসলে আছে) induction দিয়ে প্রমাণ করা যায়: প্রতিটি n-এর জন্য “0 থেকে n পর্যন্ত শর্ত মানে এমন একটিমাত্র মান-তালিকা আছে” দেখিয়ে তালিকাগুলো জোড়া দেওয়া হয়। আমরা সেটি বাদ রাখছি; সেট-তত্ত্বের বইয়ে এটি “recursion theorem” নামে পাবেন।

এই পর্বে Python-এ recursion লেখার কৌশল শেখানো হবে না; Python-এ function আর recursion-এর প্রথম পরিচয় Python প্রোগ্রামিং কোর্সের পর্ব ১৩-এ, আর call stack-সহ পূর্ণ আলোচনা DSA কোর্সের পর্ব ৭-এ। আমাদের কাজ এর গণিত: সংজ্ঞা কখন অর্থপূর্ণ, আর তার ওপর দাবি কীভাবে প্রমাণ করব।

২ · Recursive সেট — basis, নিয়ম আর “আর কিছু নয়”

Function-এর মতো সেটও recursive ভাবে বানানো যায়। একটি recursively defined set-এর সংজ্ঞায় তিনটি অংশ:

1. Basis step: কয়েকটি নির্দিষ্ট উপাদান সরাসরি সেটে আছে।
2. Recursive step: সেটে থাকা উপাদান থেকে নতুন উপাদান বানানোর নিয়ম।
3. Exclusion rule: প্রথম দুই অংশ থেকে সসীম সংখ্যক ধাপে যা পাওয়া যায়, শুধু তা-ই সেটে আছে; আর কিছু নয়।

তৃতীয় অংশ সাধারণত লেখা হয় না, তবু সবসময় ধরা থাকে। এটি না থাকলে “সব string-এর সেট”ও যেকোনো নিয়ম মেনে চলত। Exclusion rule-ই structural induction-এর ভিত্তি, পরের অংশে দেখবেন।

উদাহরণ ১ · একটি alphabet-এর ওপর সব string: Σ*

একটি alphabet Σ হলো চিহ্নের একটি সসীম সেট, যেমন Σ = {a, b}, অথবা বাজারঘরের কুপন কোডের অক্ষর-সংখ্যা। Σ-এর ওপর সব string-এর সেট Σ* (পড়া হয় “সিগমা স্টার”; * চিহ্নের নাম Kleene star):

• Basis: λ ∈ Σ*, যেখানে λ হলো empty string (শূন্য দৈর্ঘ্যের string; কোনো কোনো বইয়ে ε)।
• Recursive step: w ∈ Σ* আর x ∈ Σ হলে wx ∈ Σ* (w-এর শেষে x বসানো)।

Σ*-এর ওপর function-ও recursive ভাবে দেওয়া যায়, নিয়ম ধরে ধরে। দৈর্ঘ্য: l(λ) = 0, l(wx) = l(w) + 1. দুই string জোড়া দেওয়া, অর্থাৎ concatenation: w · λ = w, আর w · (vx) = (w · v)x.

উদাহরণ ২ · Balanced parentheses

বাজারঘরের অনুসন্ধান-বাক্সে কেউ লিখলেন (মোবাইল AND (চার্জার OR কেবল)). Query ঠিকঠাক কি না জানতে প্রথমে দেখতে হয় বন্ধনী মেলে কি না। Balanced parentheses-এর সেট B:

• Basis: λ ∈ B.
• Recursive step (নিয়ম ক): x ∈ B হলে (x) ∈ B.
• Recursive step (নিয়ম খ): x, y ∈ B হলে xy ∈ B.

যেমন () ∈ B, (()) ∈ B, ()() ∈ B. কিন্তু )( বা (() কোনো নিয়মে তৈরি হয় না, তাই exclusion rule অনুযায়ী B-তে নেই। কোনো string B-তে আছে দেখাতে হলে নিয়মের একটি শিকল দেখাতে হয়, যাকে বলে derivation. “পরে” চাপুন:

1λ          basis2()         নিয়ম ক, 13(())       নিয়ম ক, 24(())()     নিয়ম খ, 3, 2

উদাহরণ ৩ · Well-formed formula

পর্ব ০২-এ যে formula লিখেছেন, তার “ঠিক লেখা” রূপগুলোর সেটও recursive. Propositional logic-এর well-formed formula (wff):

• Basis: T, F আর প্রতিটি propositional variable (p, q, r, …) wff.
• Recursive step: E আর F′ wff হলে (¬E), (E ∧ F′), (E ∨ F′), (E → F′), (E ↔ F′)-ও wff.

তাই ((p ∧ (¬q)) → r) একটি wff, কিন্তু p ∧ ∨ q নয়। Programming language-এর syntax-ও ঠিক এভাবে লেখা হয় (BNF grammar); এর পূর্ণ আলোচনা পর্ব ৭৩ “Grammar আর formal language”-এ।

উদাহরণ ৪ · Full binary tree

একটি full binary tree-এ প্রতিটি node-এর হয় শূন্য, নয়তো ঠিক দুটি সন্তান। Recursive সংজ্ঞা:

• Basis: একটিমাত্র node (root) একটি full binary tree.
• Recursive step: T₁ আর T₂ full binary tree হলে একটি নতুন root r নিয়ে, r-এর বাঁ দিকে T₁ আর ডান দিকে T₂ জুড়ে যে tree হয়, সেটিও full binary tree. একে লিখব T₁ · T₂.

এই সংজ্ঞার সঙ্গেই দুটি function আসে, নিয়ম ধরে ধরে: height h(T) আর node-সংখ্যা n(T). Basis-এ h = 0, n = 1; recursive step-এ h(T₁ · T₂) = 1 + max(h(T₁), h(T₂)) আর n(T₁ · T₂) = 1 + n(T₁) + n(T₂). সেটের নিয়ম ধরে function-এর এমন সংজ্ঞাকে বলে structural recursion. Tree-এর সাধারণ তত্ত্ব পর্ব ৬৫ “Tree”-তে আসবে।

উদাহরণ ৫ · বাজারঘরের মেনু

শুরুর মেনুর প্রশ্নে ফিরি। মেনুর বিভাগের সেট M: basis, শুধু পণ্য আছে এমন একটি বিভাগ (উপবিভাগ নেই) M-এ আছে; recursive step, M₁, …, M_k ∈ M (k ≥ 1) হলে এদের উপবিভাগ হিসেবে নিয়ে একটি নতুন বিভাগও M-এ আছে। এখানে নিয়মটি যেকোনো সংখ্যক ইনপুট নেয়, তবু structural induction একইভাবে চলে। দুটি function: গভীরতা d (basis-এ 0; নইলে 1 + সবচেয়ে গভীর উপবিভাগের d) আর মোট বিভাগ-সংখ্যা c (basis-এ 1; নইলে 1 + c(M₁) + … + c(M_k)).

1. Basis: c = 1 আর d = 0, তাই 1 ≥ 0 + 1.
2. Recursive step: X-এর উপবিভাগ M₁, …, M_k, প্রতিটিতে দাবি সত্য ধরি। M_j সবচেয়ে গভীর উপবিভাগ, তাই d(X) = 1 + d(M_j).
3. সব c মান ধনাত্মক, তাই c(X) = 1 + Σ c(M_i) ≥ 1 + c(M_j) ≥ 1 + d(M_j) + 1 = d(X) + 1. ∎

অর্থাৎ ৫ স্তর গভীর মেনুতে অন্তত ৬টি বিভাগ থাকবেই; সমতা হয় যখন মেনু একটি সরল শিকল, প্রতিটি বিভাগে একটিমাত্র উপবিভাগ।

৩ · Structural induction — প্রতিটি নিয়মের জন্য একটি ক্ষেত্র

Recursive সেটের প্রতিটি উপাদানের ওপর দাবি প্রমাণ করার পদ্ধতি structural induction. এটি পর্ব ১০-এর mathematical induction-এর সরাসরি সম্প্রসারণ: সেখানে ℕ-কে ভাবা হয় “0 আছে; n থাকলে n + 1 আছে” দিয়ে বানানো সেট হিসেবে।

কেন এটি valid: exclusion rule অনুযায়ী S-এর প্রতিটি উপাদান সসীম সংখ্যক নিয়ম-প্রয়োগে তৈরি। Q(n): “যে উপাদান সর্বোচ্চ n ধাপের derivation-এ তৈরি হয়, তাতে P সত্য”। (১) থেকে Q(0); (২) থেকে Q(0), …, Q(n) সত্য হলে Q(n + 1), কারণ শেষ ধাপের ইনপুটগুলো আরও কম ধাপে তৈরি। তাই strong induction-এ সব n-এর জন্য Q(n), অর্থাৎ সব উপাদানে P. মানে structural induction নতুন কোনো স্বতঃসিদ্ধ নয়; derivation-এর দৈর্ঘ্যের ওপর সাধারণ induction-ই।

প্রমাণ লেখার আগে নিয়ম তিনটির দিকে তাকান: basis-এর দৈর্ঘ্য 0, নিয়ম ক 2 যোগ করে, নিয়ম খ দুটি দৈর্ঘ্য যোগ করে। প্রমাণটি ঠিক এই তিন পর্যবেক্ষণ, তিন ক্ষেত্রে সাজানো। Stepper-এ প্রমাণটি ধাপে ধাপে, পাশে (())()-এর ওপর মিলিয়ে দেখা:

1P(s): l(s) জোড়2basis: s = λ3নিয়ম ক: s = (x)4নিয়ম খ: s = xy

এবার Σ*-এ একটি প্রমাণ, যেখানে recursion চলে দ্বিতীয় string-এর ওপর। এটি দেখায়, কোন variable-এর ওপর induction চালাবেন, সেটি বাছাই করাও প্রমাণের অংশ।

প্রমাণ: w স্থির রেখে v-এর ওপর structural induction. P(v): “l(w · v) = l(w) + l(v)”.

1. Basis, v = λ: concatenation-এর সংজ্ঞায় w · λ = w, তাই l(w · λ) = l(w) = l(w) + 0 = l(w) + l(λ).
2. Recursive step: ধরি v ∈ Σ*, x ∈ Σ, আর P(v) সত্য। দেখাতে হবে P(vx).
3. Concatenation-এর সংজ্ঞায় w · (vx) = (w · v)x, তাই দৈর্ঘ্যের সংজ্ঞায় l(w · (vx)) = l(w · v) + 1.
4. Inductive hypothesis-এ l(w · v) = l(w) + l(v), তাই এটি l(w) + l(v) + 1.
5. দৈর্ঘ্যের সংজ্ঞায় l(vx) = l(v) + 1, তাই মান l(w) + l(vx). P(vx) সত্য। ∎

w-এর ওপর induction চালাতে চাইলে আটকে যেতেন: সংজ্ঞা শেষ অক্ষর ধরে ভাঙে, আর w-এর শেষ অক্ষর w · v-এর শেষে থাকে না। সংজ্ঞা যেদিক থেকে ভাঙে, induction-ও সেদিক থেকে চালান।

পরের উপপাদ্যটি দেখায়, কেন )( বা ())(() B-তে থাকতে পারে না। একটি string s-এর শুরুর অংশ (prefix) মানে s-এর প্রথম কয়েকটি চিহ্ন, শূন্যটি বা সবগুলো হতেও পারে।

প্রমাণ: d(u) = u-তে “(”-এর সংখ্যা − “)”-এর সংখ্যা। P(s): s-এর প্রতিটি prefix u-তে d(u) ≥ 0, আর d(s) = 0.

1. Basis s = λ: একমাত্র prefix λ, d(λ) = 0. P(λ) সত্য।
2. নিয়ম ক, s = (x), P(x) ধরে: s-এর prefix হয় λ (d = 0), নয়তো “(” আর তারপর x-এর একটি prefix v (d = 1 + d(v) ≥ 1), নয়তো পুরো s (d = 1 + d(x) − 1 = 0). সবগুলো ≥ 0, আর d(s) = 0.
3. নিয়ম খ, s = xy, P(x) আর P(y) ধরে: s-এর prefix হয় x-এর একটি prefix (d ≥ 0, P(x) থেকে), নয়তো x-এর পরে y-এর একটি prefix v (d = d(x) + d(v) = 0 + d(v) ≥ 0). আর d(s) = d(x) + d(y) = 0.
4. সব ক্ষেত্রে P টিকে থাকে, তাই B-এর প্রতিটি s-এ P(s) সত্য। ∎

())(()-এর prefix ())-এ d = 1 − 2 = −1 < 0, তাই এটি B-তে নেই, যদিও দৈর্ঘ্য জোড় আর মোট বন্ধনী সমান। উল্টো দিকটিও সত্য (এই দুই শর্ত মানা প্রতিটি string B-তে আছে), তবে তার প্রমাণ string-এর দৈর্ঘ্যের ওপর strong induction, আমরা বাদ রাখছি। আমাদের scratch হিসাবে দৈর্ঘ্য 8 পর্যন্ত সব বন্ধনী-string-এ দুই বর্ণনা হুবহু মিলেছে।

খুঁজে দেখা — Python দিয়ে ছোট ক্ষেত্র

প্রমাণ লেখার আগে দাবিটি ছোট ক্ষেত্রে পরীক্ষা করা ভালো অভ্যাস। নিচের ব্লক নিয়ম অনুসরণ করেই Σ* আর B তৈরি করে (দৈর্ঘ্য 8 পর্যন্ত), দাবিগুলো যাচাই করে, আর একটি মিথ্যা দাবির counterexample খোঁজে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from collections import Counter

# Σ* over {a, b} by the rules: basis λ, step w -> wx
level, sigma = [""], [""]
for _ in range(8):
    level = [w + x for w in level for x in "ab"]
    sigma += level
print("Σ* up to length 8:", len(sigma), "strings; 2^9 - 1 =", 2**9 - 1)

# B: basis λ; rule A: x -> (x); rule B: x, y -> xy
def balanced_upto(L):
    B = {""}
    while True:
        new = set(B)
        new |= {"(" + x + ")" for x in B if len(x) + 2 <= L}
        new |= {x + y for x in B for y in B if len(x + y) <= L}
        if new == B:              # closed under both rules
            return B
        B = new

B = balanced_upto(8)
print("length: count", sorted(Counter(map(len, B)).items()))
print("every length even?", all(len(s) % 2 == 0 for s in B))

# false claim: "every nonempty s in B looks like (x) with x in B"
bad = sorted((s for s in B if s and not (s[0] == "(" and
              s[-1] == ")" and s[1:-1] in B)), key=lambda s: (len(s), s))
print("counterexamples:", bad[:3], "... total", len(bad))

Σ* up to length 8: 511 strings; 2^9 - 1 = 511
length: count [(0, 1), (2, 1), (4, 2), (6, 5), (8, 14)]
every length even? True
counterexamples: ['()()', '(())()', '()(())'] ... total 13

ভুল প্রমাণ — কোন ক্ষেত্র বাদ পড়েছে?

একজন শিক্ষার্থী লিখলেন: “দাবি: B-এর প্রতিটি অশূন্য string দেখতে (x), যেখানে x ∈ B. প্রমাণ: structural induction. Basis λ অশূন্য নয়, তাই কিছু দেখাতে হবে না। নিয়ম ক: নতুন string (x), x ∈ B; এটি সংজ্ঞা অনুযায়ীই (x) আকারের। ∎”

৪ · Full binary tree — node আর height-এর সম্পর্ক

বাজারঘরের পণ্য-অনুসন্ধানের একটি সিদ্ধান্ত-গাছ ভাবুন: প্রতিটি প্রশ্নে দুটি উত্তর (হ্যাঁ/না), আর শেষে একটি পণ্য-তালিকা। এটি একটি full binary tree. গাছের height মানে সর্বোচ্চ কয়টি প্রশ্ন করতে হয়। প্রশ্ন: h প্রশ্নের মধ্যে গাছে সর্বোচ্চ কয়টি node রাখা যায়? প্রথমে ছোট ক্ষেত্র: h = 0-এ 1টি node; h = 1-এ 3টি; h = 2-এ বড়জোর 7টি। অনুমান: 2^h+1 − 1.

প্রমাণ (structural induction):

1. Basis: T একক node. n(T) = 1, h(T) = 0, আর 2⁰⁺¹ − 1 = 1. তাই 1 ≤ 1, দাবি সত্য।
2. Recursive step: T = T₁ · T₂. Inductive hypothesis: n(T₁) ≤ 2^h(T₁)+1 − 1 আর n(T₂) ≤ 2^h(T₂)+1 − 1.
3. n-এর recursive সংজ্ঞায় n(T) = 1 + n(T₁) + n(T₂).
4. Inductive hypothesis বসিয়ে: n(T) ≤ 1 + (2^h(T₁)+1 − 1) + (2^h(T₂)+1 − 1).
5. M = max(h(T₁), h(T₂)) লিখি। 2^x বর্ধমান, তাই প্রতিটি পদ ≤ 2^M+1; ফলে n(T) ≤ 2 · 2^M+1 − 1 = 2^M+2 − 1.
6. h-এর সংজ্ঞায় h(T) = 1 + M, তাই M + 2 = h(T) + 1, আর n(T) ≤ 2^h(T)+1 − 1. ∎

ধাপ ৫-ই প্রমাণের আসল চাবি: দুটি ভিন্ন height-কে বড়টি দিয়ে ঢাকা। সমতা হয় ঠিক তখন, যখন দুই subtree একই height-এর আর নিজেরাও “পূর্ণ” (perfect binary tree). নিচের ব্লক height 3 পর্যন্ত সব full binary tree বানিয়ে সীমাটি পরীক্ষা করে:

from collections import Counter

# () is a single node; (T1, T2) is a new root over T1 and T2
def trees(h):                  # all full binary trees of height <= h
    if h == 0:
        return [()]
    smaller = trees(h - 1)
    return [()] + [(a, b) for a in smaller for b in smaller]

def n(t):
    return 1 if t == () else 1 + n(t[0]) + n(t[1])

def ht(t):
    return 0 if t == () else 1 + max(ht(t[0]), ht(t[1]))

def leaves(t):
    return 1 if t == () else leaves(t[0]) + leaves(t[1])

T = trees(3)
print("full binary trees with height <= 3:", len(T))
for h in range(4):
    sizes = Counter(n(t) for t in T if ht(t) == h)
    print(f"h={h}: n -> count {dict(sorted(sizes.items()))}",
          f"| bound {2 ** (h + 1) - 1}")
print("n(T) <= 2^(h+1) - 1 for all?",
      all(n(t) <= 2 ** (ht(t) + 1) - 1 for t in T))
print("leaves = internal + 1 for all?",
      all(leaves(t) == n(t) - leaves(t) + 1 for t in T))

full binary trees with height <= 3: 26
h=0: n -> count {1: 1} | bound 1
h=1: n -> count {3: 1} | bound 3
h=2: n -> count {5: 2, 7: 1} | bound 7
h=3: n -> count {7: 4, 9: 6, 11: 6, 13: 4, 15: 1} | bound 15
n(T) <= 2^(h+1) - 1 for all? True
leaves = internal + 1 for all? True

নিচের সীমা আর একটি পরীক্ষার হিসাব

ওপরের সীমার পাশাপাশি একটি নিচের সীমাও আছে: n(T) ≥ 2h(T) + 1. Basis-এ 1 ≥ 0 + 1. Recursive step-এ ধরি h(T₁) ≥ h(T₂) (অন্যথায় নাম বদলে নিন; এটি “without loss of generality”-র সঠিক ব্যবহার, কারণ দাবিটি দুই subtree-তে প্রতিসম)। তাহলে h(T) = 1 + h(T₁), আর hypothesis থেকে n(T) = 1 + n(T₁) + n(T₂) ≥ 1 + (2h(T₁) + 1) + 1 = 2(h(T₁) + 1) + 1 = 2h(T) + 1, যেখানে n(T₂) ≥ 1 ব্যবহার হয়েছে। ∎

পরীক্ষার ধাঁচের প্রশ্ন: height 3-এর full binary tree-তে কয়টি node থাকতে পারে? দুই সীমা মিলিয়ে 7 ≤ n ≤ 15, আর অনুশীলন ১-এর ফল অনুযায়ী n বিজোড়। তাই সম্ভাব্য মান 7, 9, 11, 13, 15; full_trees.py-র h = 3 সারিতে ঠিক এই পাঁচটি মানই এসেছে। Height 4-এ ৮টি node অসম্ভব, কারণ 8 < 2 · 4 + 1 = 9.

৫ · Structural recursion-এ মূল্যায়ন — একটি formula-র মান

Recursive সেটের ওপর function সংজ্ঞায়িত করতে প্রতিটি নিয়মের জন্য একটি সূত্র দিলেই হয়। Wff-এর মান (truth value) তার একটি উদাহরণ: variable-এর মান দেওয়া থাকলে v(p) টেবিল থেকে; v((¬E)) = ¬v(E); v((E ∧ F′)) = v(E) ∧ v(F′); বাকি connective-গুলোও একইভাবে। Python interpreter, ক্যালকুলেটর আর spreadsheet ঠিক এভাবে expression-এর মান বের করে: ভেতর থেকে বাইরে।

একটি সূক্ষ্ম কথা: এই সংজ্ঞা function দেয় কারণ প্রতিটি wff একটিমাত্র উপায়ে নিয়ম থেকে তৈরি (unique readability). বন্ধনী না থাকলে p ∧ q ∨ r দুইভাবে পড়া যেত, আর মান দুই রকম হতে পারত। বাজারঘরের একটি কুপন-নিয়ম: “(নতুন গ্রাহক এবং ঢাকার বাইরে নয়) হলে (প্রি-অর্ডার অথবা ঢাকার বাইরে)”। p = নতুন গ্রাহক (T), q = ঢাকার বাইরে (F), r = প্রি-অর্ডার (F):

1p, q, r        variable2(¬q)            ¬ নিয়ম3(p ∧ (¬q))      ∧ নিয়ম4(r ∨ q)         ∨ নিয়ম5(… → …)         → নিয়ম

প্রমাণ: L(E) আর R(E) যথাক্রমে বাঁ আর ডান বন্ধনীর সংখ্যা; P(E): L(E) = R(E).

1. Basis: T, F বা একটি variable-এ কোনো বন্ধনী নেই, তাই L = R = 0.
2. ¬ নিয়ম: ধরি L(E) = R(E). (¬E)-তে একটি নতুন “(” আর একটি নতুন “)”, তাই L = L(E) + 1 = R(E) + 1 = R.
3. দুই-অংশের নিয়ম (∧, ∨, →, ↔ চারটিই একই আকারের): ধরি L(E) = R(E) আর L(F′) = R(F′). (E ∗ F′)-এ L = L(E) + L(F′) + 1 = R(E) + R(F′) + 1 = R, যেখানে ∗ যেকোনো একটি connective; connective চিহ্নে বন্ধনী নেই।
4. সব নিয়মে P টিকে থাকে, তাই structural induction অনুযায়ী প্রতিটি wff-এ L = R. ∎

৬ · ℕ×ℕ-এ induction — lexicographic order আর Ackermann

কিছু recursion দুই argument নিয়ে চলে। বাজারঘরের গুদামে র‍্যাকের তাক m আর খোপ n দিয়ে চিহ্নিত; একটি গণনা a(m, n) এভাবে সংজ্ঞায়িত:

a(0, 0) = 0;   a(m, 0) = a(m − 1, 0) + 1 যখন m > 0;   a(m, n) = a(m, n − 1) + n যখন n > 0.

একটি ডাক একটি জোড়াকে “ছোট” জোড়ায় নিয়ে যায়। কোন অর্থে ছোট? Lexicographic order (অভিধান-ক্রম): (m′, n′) ≺ (m, n) যদি m′ < m, অথবা m′ = m আর n′ < n. অভিধানে যেমন প্রথম অক্ষর আগে তুলনা হয়, পরে দ্বিতীয়টি।

নীতিটি কেন ঠিক: P মিথ্যা এমন জোড়ার সেট অশূন্য হলে তার একটি ক্ষুদ্রতম উপাদান থাকত; তার চেয়ে ছোট সব জোড়ায় P সত্য, তাই অনুমান অনুযায়ী সেখানেও P সত্য, বিরোধ। এটিই পর্ব ১১-এর minimal counterexample কৌশল, জোড়ার ওপর।

আবিষ্কারের পথ: হাতে কয়েকটি মান: a(1, 0) = 1, a(2, 0) = 2, তাই a(m, 0) = m মনে হয়। তারপর a(2, 1) = 2 + 1 = 3, a(2, 2) = 3 + 2 = 5, a(2, 3) = 5 + 3 = 8: m-এর সঙ্গে 1 + 2 + … + n যোগ হচ্ছে। সেখান থেকেই অনুমান। প্রমাণ (generalized induction):

1. Basis (0, 0): a(0, 0) = 0 = 0 + 0 · 1/2.
2. ধরি (m, n) ≠ (0, 0), আর ≺-ছোট সব জোড়ায় সূত্রটি সত্য (inductive hypothesis).
3. ক্ষেত্র n = 0 (তাই m > 0): (m − 1, 0) ≺ (m, 0). সংজ্ঞা আর hypothesis থেকে a(m, 0) = a(m − 1, 0) + 1 = (m − 1) + 0 + 1 = m = m + 0 · 1/2.
4. ক্ষেত্র n > 0: (m, n − 1) ≺ (m, n). তাই a(m, n) = a(m, n − 1) + n = m + (n − 1)n/2 + n.
5. বীজগণিত: (n − 1)n/2 + n = (n² − n + 2n)/2 = n(n + 1)/2. তাই a(m, n) = m + n(n + 1)/2.
6. দুই ক্ষেত্র সব (m, n) ≠ (0, 0) ঢাকে; নীতি ৬.১ অনুযায়ী সূত্রটি সব জোড়ায় সত্য। ∎

Lexicographic order-এর শক্তি আসল বোঝা যায় Ackermann function-এ (এখানে Ackermann–Péter রূপ): A(0, n) = n + 1; A(m, 0) = A(m − 1, 1) যখন m > 0; A(m, n) = A(m − 1, A(m, n − 1)) যখন m, n > 0. শেষ নিয়মে ভেতরের ডাকের ফল A(m, n − 1) বিশাল হতে পারে, তবু বাইরের ডাকে প্রথম argument m − 1, তাই lexicographic অর্থে জোড়া ছোট হয়। ফলে generalized induction দিয়েই প্রমাণ হয় যে প্রতিটি ডাক থামে।

from functools import lru_cache

@lru_cache(maxsize=None)
def a(m, n):
    if m == 0 and n == 0:
        return 0
    if n == 0:
        return a(m - 1, 0) + 1
    return a(m, n - 1) + n

print("a(2,3) =", a(2, 3), " a(3,2) =", a(3, 2))
print("a(m,n) == m + n(n+1)/2 for all m, n < 30?",
      all(a(m, n) == m + n * (n + 1) // 2
          for m in range(30) for n in range(30)))

calls = 0
def A(m, n):                     # Ackermann-Peter function
    global calls
    calls += 1
    if m == 0:
        return n + 1
    if n == 0:
        return A(m - 1, 1)
    return A(m - 1, A(m, n - 1))

for m in range(4):
    row = []
    for n in range(5):
        calls = 0
        value = A(m, n)
        row.append(f"{value}[{calls}]")
    print(f"A({m}, n), n=0..4:", " ".join(row))

a(2,3) = 8  a(3,2) = 6
a(m,n) == m + n(n+1)/2 for all m, n < 30? True
A(0, n), n=0..4: 1[1] 2[1] 3[1] 4[1] 5[1]
A(1, n), n=0..4: 2[2] 3[4] 4[6] 5[8] 6[10]
A(2, n), n=0..4: 3[5] 5[14] 7[27] 9[44] 11[65]
A(3, n), n=0..4: 5[15] 13[106] 29[541] 61[2432] 125[10307]

৭ · Fibonacci-র দুটি তথ্য — বৃদ্ধির হার আর Cassini-র সূত্র

Fibonacci সংখ্যা কত দ্রুত বাড়ে? α = (1 + √5)/2 ≈ 1.618 (সোনালি অনুপাত, golden ratio) নিন। এর মূল ধর্ম α² = α + 1, কারণ α হলো x² − x − 1 = 0-এর ধনাত্মক মূল। প্রথমে Python-এ খোঁজ, তারপর প্রমাণ:

from math import sqrt

f = [0, 1]                          # f(0) = 0, f(1) = 1
for n in range(2, 61):
    f.append(f[n - 1] + f[n - 2])   # f(n) = f(n-1) + f(n-2)

alpha = (1 + sqrt(5)) / 2
print("alpha =", alpha, " alpha^2 =", alpha ** 2, " alpha+1 =", alpha + 1)

# scratch work: from which n does f(n) > alpha^(n-2) hold?
for n in range(7):
    print(n, f[n], round(alpha ** (n - 2), 3), f[n] > alpha ** (n - 2))
print("f(n) > alpha^(n-2) for all 3 <= n <= 60?",
      all(f[n] > alpha ** (n - 2) for n in range(3, 61)))

# Cassini: f(n+1) * f(n-1) - f(n)^2 == (-1)^n
vals = [f[n + 1] * f[n - 1] - f[n] ** 2 for n in range(1, 60)]
print("Cassini values, n = 1..8:", vals[:8])
print("Cassini holds for 1 <= n <= 59?",
      all(v == (-1) ** n for n, v in zip(range(1, 60), vals)))
print("f(60) =", f[60])

alpha = 1.618033988749895  alpha^2 = 2.618033988749895  alpha+1 = 2.618033988749895
0 0 0.382 False
1 1 0.618 True
2 1 1.0 False
3 2 1.618 True
4 3 2.618 True
5 5 4.236 True
6 8 6.854 True
f(n) > alpha^(n-2) for all 3 <= n <= 60? True
Cassini values, n = 1..8: [-1, 1, -1, 1, -1, 1, -1, 1]
Cassini holds for 1 <= n <= 59? True
f(60) = 1548008755920

প্রমাণ (strong induction): P(n): f(n) > αⁿ⁻².

1. Basis n = 3: f(3) = 2 > α ≈ 1.618. Basis n = 4: f(4) = 3 > α² = α + 1 ≈ 2.618. দুটি basis লাগে, কারণ ধাপে দুই আগের মান ব্যবহার হবে।
2. ধরি k ≥ 4, আর 3 ≤ j ≤ k সব j-এর জন্য P(j) সত্য। দেখাতে হবে P(k + 1).
3. α² = α + 1-কে α^k−3 দিয়ে গুণ করে: α^k−1 = α^k−2 + α^k−3.
4. k ≥ 4 বলে k − 1 ≥ 3, তাই hypothesis P(k) আর P(k − 1) দুটোই খাটে: α^k−2 < f(k) আর α^k−3 < f(k − 1).
5. যোগ করে: α^k−1 < f(k) + f(k − 1) = f(k + 1), Fibonacci-র সংজ্ঞায়। এটিই P(k + 1). ∎

অর্থাৎ Fibonacci সংখ্যা exponential হারে বাড়ে। এর একটি বিখ্যাত প্রয়োগ Lamé-র উপপাদ্য: Euclid-এর algorithm-এ ভাগের ধাপ ছোট সংখ্যাটির দশমিক অঙ্কের পাঁচ গুণের বেশি হয় না; পর্ব ২১-এ।

প্রমাণ (induction):

1. Basis n = 1: f(2) · f(0) − f(1)² = 1 · 0 − 1 = −1 = (−1)¹.
2. ধরি কোনো k ≥ 1-এর জন্য f(k + 1) f(k − 1) − f(k)² = (−1)^k.
3. f(k + 2) = f(k + 1) + f(k) বসিয়ে: f(k + 2) f(k) − f(k + 1)² = f(k + 1) f(k) + f(k)² − f(k + 1)².
4. f(k + 1)² = f(k + 1)(f(k) + f(k − 1)) লিখে: = f(k + 1) f(k) + f(k)² − f(k + 1) f(k) − f(k + 1) f(k − 1) = f(k)² − f(k + 1) f(k − 1).
5. Hypothesis অনুযায়ী এটি −(−1)^k = (−1)^k+1. ∎

উদাহরণ n = 10: f(11) · f(9) − f(10)² = 89 · 34 − 55² = 3026 − 3025 = 1 = (−1)¹⁰. Fibonacci-র মতো recurrence-এর বন্ধ রূপ (Binet-এর সূত্র) পর্ব ৪৪ আর ৪৫-এ আসবে।

৮ · Recursive algorithm ঠিক কি না — induction-ই উত্তর

একটি recursive algorithm নিজেই একটি recursive সংজ্ঞা, তাই তার সঠিকতার স্বাভাবিক প্রমাণ induction, সাধারণত ইনপুটের আকারের ওপর strong induction. ছাঁচটি সবসময় এক: (১) base case-এ ফল ঠিক; (২) ধরে নিন সব ছোট ইনপুটে recursive ডাক ঠিক ফল দেয়; (৩) দেখান সেই ফলগুলো জুড়ে এই ইনপুটেও ফল ঠিক; (৪) দেখান প্রতিটি ডাক সত্যিই ছোট ইনপুটে যায়, যাতে algorithm থামে।

প্রমাণ (খণ্ডের দৈর্ঘ্য n = hi − lo + 1-এর ওপর strong induction):

1. Basis n ≤ 0: খণ্ড ফাঁকা, x সেখানে নেই, আর algorithm “নেই” বলে। ঠিক।
2. ধরি n ≥ 1, আর দৈর্ঘ্য < n-এর সব খণ্ডে algorithm ঠিক (hypothesis). lo ≤ mid ≤ hi, তাই A[mid] খণ্ডের ভেতরে।
3. A[mid] = x হলে mid ফেরত দেয়: ঠিক।
4. A[mid] < x হলে, A সাজানো বলে A[lo..mid]-এর সব মান ≤ A[mid] < x; তাই x থাকলে শুধু A[mid+1..hi]-তে। এই খণ্ডের দৈর্ঘ্য hi − mid < n, তাই hypothesis অনুযায়ী ডাকটি ঠিক উত্তর দেয়।
5. A[mid] > x হলে প্রতিসমভাবে x থাকলে শুধু A[lo..mid−1]-এ, দৈর্ঘ্য mid − lo < n; আবার hypothesis.
6. তিন ক্ষেত্রেই ফল ঠিক, আর প্রতিটি ডাক কঠোরভাবে ছোট খণ্ডে যায়, তাই algorithm থামে। ∎

Merge sort-এর প্রমাণের রূপরেখা: দৈর্ঘ্য n ≤ 1 হলে তালিকা আগেই সাজানো। n ≥ 2 হলে দুই অর্ধেকের দৈর্ঘ্য ⌊n/2⌋ আর ⌈n/2⌉, দুটোই < n; hypothesis অনুযায়ী recursive ডাক দুটি তাদের সাজায়। এরপর merge যে দুই সাজানো তালিকা থেকে একটি সাজানো তালিকা দেয়, তা merge-এর loop-এর একটি invariant দিয়ে আলাদা প্রমাণ করতে হয়। তাহলে পুরো তালিকা সাজানো হয়, আর strong induction অনুযায়ী সব n-এর জন্য merge sort ঠিক। এখানে একটি খুঁটিনাটি গুরুত্বপূর্ণ: n ≥ 2-এর শর্ত না থাকলে n = 1-এ এক অর্ধেকের দৈর্ঘ্য 1 হয়ে যেত, অর্থাৎ ইনপুট ছোট হতো না, আর hypothesis ব্যবহার করা যেত না। Base case-এর সীমা আর “ডাক ছোট ইনপুটে যায়” শর্ত একে অপরের সঙ্গে বাঁধা। এই loop invariant-এর যুক্তি পর্ব ১৩ “Program-এর সঠিকতা”-য়, আর algorithm-এর দিক থেকে DSA কোর্সের পর্ব ৩, পর্ব ১৮ আর পর্ব ২১-এ। চলার সময়ের recurrence T(n) = 2T(n/2) + Θ(n)-এর সমাধান DSA কোর্সের পর্ব ৮-এ।

৯ · AI-এর যুগে — AI-এর লেখা induction প্রমাণ যাচাই

AI সহকারী structural induction-এর প্রমাণ দ্রুত লিখে দেয়, আর লেখার ধরন নিখুঁত দেখায়। কিন্তু এই বিষয়ে তার ভুলগুলো চেনা ছাঁচের:

AI-এর প্রমাণ হাতে পেলে — যাচাইয়ের চেকলিস্ট

• সংজ্ঞার প্রতিটি basis রূপ আর প্রতিটি নিয়মের জন্য একটি ক্ষেত্র আছে
• Hypothesis শুধু নিয়মের ইনপুট উপাদানে (বা ছোট মানে) ব্যবহার হয়েছে, নতুন উপাদানে নয়
• Basis-এর মান Python-এ ছোট ক্ষেত্রে চালিয়ে মিলিয়েছি; শর্ত (যেমন n ≥ 3) সঠিক
• প্রতিটি recursive ডাকে কোন মাপ কমে, তা চিহ্নিত করেছি
• নিয়ম ধরে ছোট সব উপাদান বানিয়ে counterexample খুঁজেছি
• উল্লেখ করা উপপাদ্য আর তার শর্ত একটি বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি