ম্যাথমেটিক্যাল ইনডাকশন ও প্রুফ টেকনিক

১ · ম্যাথমেটিক্যাল ইনডাকশন

ম্যাথমেটিক্যাল ইনডাকশনMathematical Inductionএকটি স্টেটমেন্ট P(n) সব প্রাকৃতিক সংখ্যা n ≥ base-এর জন্য সত্য প্রমাণ করার একটি টেকনিক — base case + inductive step। হলো একটি স্টেটমেন্ট $P(n)$ সব $n \geq \text{base case}$-এর জন্য প্রমাণ করার একটি টেকনিক — এই কোর্সের প্রায় প্রতিটি বড় থিওরেম এই টেকনিকের কোনো না কোনো রূপ ব্যবহার করে ( discrete-math L06-এ পড়ে থাকলে সরাসরি পুনরাবৃত্তি, নতুন করে করছি না)। এটি দুটি অংশে গঠিত —

1. Base case: $P(\text{base})$ সরাসরি (সাধারণত হাতে-গোনা যাচাইযোগ্য) প্রমাণ করা।
2. Inductive step: inductive hypothesis — $P(k)$ সত্য ধরে নিয়ে — দেখানো যে $P(k+1)$-ও সত্য হতে বাধ্য।

এই দুটো মিলিয়ে $P(\text{base})$, তারপর $P(\text{base}) \implies P(\text{base}+1)$, তারপর $P(\text{base}+1) \implies P(\text{base}+2)$ ... — একটি ডমিনো-চেইনের মতো, যা সব $n \geq \text{base}$-এর জন্য $P(n)$ প্রতিষ্ঠা করে।

২ · স্ট্রাকচারাল ইনডাকশন

স্ট্রাকচারাল ইনডাকশনStructural Inductionইন্টিজারের উপর নয়, বরং রিকার্সিভভাবে সংজ্ঞায়িত বস্তুর (স্ট্রিং, পার্স ট্রি) গঠনের উপর ইনডাকশন। হলো ইনডাকশনের একটি রূপান্তর যেখানে ইন্টিজারের বদলে একটি রিকার্সিভভাবে-সংজ্ঞায়িত বস্তুর গঠনের উপর ইনডাকশন করা হয় — এই কোর্সে সবচেয়ে বেশি ব্যবহৃত ফর্ম, কারণ স্ট্রিং (L02), পার্স ট্রি (M4), এমনকি টুরিং মেশিন কনফিগারেশন (M8) — সবই রিকার্সিভভাবে সংজ্ঞায়িত। উদাহরণস্বরূপ, $\Sigma^*$-এর সব স্ট্রিং-এর জন্য একটি প্রপার্টি প্রমাণ করতে —

1. Base case: প্রপার্টিটি $\varepsilon$-এর জন্য সত্য প্রমাণ করা।
2. Inductive step: প্রপার্টিটি একটি স্ট্রিং $w$-এর জন্য সত্য ধরে নিয়ে, দেখানো যে এটি $wa$ (যেকোনো সিম্বল $a$ যোগ করে তৈরি বড় স্ট্রিং)-এর জন্যও সত্য।

যেহেতু $\Sigma^*$-এর প্রতিটি স্ট্রিং $\varepsilon$ থেকে শুরু করে বারবার একটি সিম্বল যোগ করে তৈরি করা যায় (L02-এর রিকার্সিভ সংজ্ঞা), এই দুই ধাপ মিলিয়ে সব স্ট্রিং-এর জন্য প্রপার্টিটি প্রতিষ্ঠিত হয়।

৩ · প্রুফ বাই কনট্রাডিকশন

প্রুফ বাই কনট্রাডিকশনProof by Contradictionযা প্রমাণ করতে চাই তার নেগেশন ধরে নিয়ে একটি লজিক্যাল বিরোধ বের করে মূল দাবিটি সত্য প্রমাণ করা। হলো এই কোর্সের অন্য প্রধান প্রুফ টেকনিক — বিশেষত non-regularity (M3) ও undecidability (M9) প্রমাণে প্রায় সবসময় ব্যবহৃত হয়। টেমপ্লেটটি —

1. যা প্রমাণ করতে চাই তার নেগেশন ধরে নাও।
2. সেই নেগেশন থেকে যৌক্তিকভাবে অগ্রসর হও।
3. একটি লজিক্যাল বিরোধ (contradiction) — এমন কিছু যা একইসাথে সত্য ও মিথ্যা, বা কোনো পূর্বপ্রতিষ্ঠিত সত্যকে লঙ্ঘন করে — খুঁজে বের করো।
4. যেহেতু নেগেশন থেকে একটি বিরোধ আসে, নেগেশনটি মিথ্যা হতে বাধ্য — তাই মূল স্টেটমেন্টটি সত্য।

৪ · Worked Example — $|w^R| = |w|$

দাবি: সব স্ট্রিং $w \in \Sigma^*$-এর জন্য, $|w^R| = |w|$ (উল্টো করলে length অপরিবর্তিত থাকে)। স্ট্রাকচারাল ইনডাকশন দিয়ে প্রমাণ —

৫ · Python-এ ইনডাকটিভ Reversal ও একটি কনট্রাডিকশন-চেকার

নিচের কোড সেলে ঠিক উপরের ইনডাকটিভ সংজ্ঞা অনুযায়ী (base case: $\varepsilon$, inductive case: $wa \to a \cdot \text{reverse}(w)$) একটি reverse_string ফাংশন লেখা হচ্ছে (Python-এর স্লাইসিং শর্টকাট ব্যবহার না করে), তারপর একটি ছোট্ট প্রুফ-বাই-কনট্রাডিকশন-স্টাইল চেকার — একটি বিখ্যাত উদাহরণ, অয়লারের "$n^2-n+41$ সবসময় মৌলিক" দাবির প্রথম কাউন্টার-এক্সাম্পল খুঁজে বের করছে।

def reverse_string(s):
    """base case: khali string nijei fire ase; inductive case: reverse(s[1:]) + s[0]"""
    if s == "":
        return s
    return reverse_string(s[1:]) + s[0]

test_strings = ["", "a", "ab", "hello", "0110", "1101001"]
print(f"{'w':10s} | {'reverse(w)':12s} | |w| | |reverse(w)| | মিলছে?")
print("-" * 55)
all_ok = True
for s in test_strings:
    r = reverse_string(s)
    ok = len(r) == len(s)
    all_ok = all_ok and ok
    print(f"{s!r:10s} | {r!r:12s} | {len(s):3d} | {len(r):11d} | {'হ্যাঁ' if ok else 'না'}")
print()
print("সব টেস্ট স্ট্রিং-এ |w^R| = |w| সন্তুষ্ট? (ইনডাকটিভ দাবির স্পট-চেক):", all_ok)

def is_prime(n):
    if n < 2:
        return False
    for d in range(2, int(n ** 0.5) + 1):
        if n % d == 0:
            return False
    return True

def property_holds(n):
    # daabi: shokol n >= 1 -er jonno, n^2 - n + 41 ekti mowlik shonkha
    return is_prime(n * n - n + 41)

def check_counterexample(claimed_n, property_fn):
    """dile ekti 'counterexample'-er dabi, jachai kore eta shotti property longhon kore kina"""
    return not property_fn(claimed_n)

print()
print("দাবি: সব n >= 1-এর জন্য, n^2 - n + 41 একটি মৌলিক সংখ্যা (Euler's prime-generating polynomial)")
for n in [1, 5, 10, 40, 41]:
    value = n * n - n + 41
    is_counterexample = check_counterexample(n, property_holds)
    print(f"n={n:3d} -> n^2-n+41 = {value:5d}, মৌলিক? {is_prime(value)}, contradiction/counterexample? {is_counterexample}")