Strong induction আর well-ordering

১ · সাধারণ induction কোথায় আটকে যায়

পর্ব ১০ “Mathematical induction — এক ধাপ থেকে অসীম পর্যন্ত”-এ ছাঁচটি ছিল: P(1) সত্য, আর প্রতিটি k-এর জন্য P(k) → P(k + 1); তাহলে সব n-এ P(n) সত্য। ডমিনোর সারির মতো: প্রথমটি পড়ে, আর প্রতিটি ডমিনো ঠিক পরেরটিকে ফেলে।

এবার বাজারঘরের হিসাব বিভাগের একটি প্রশ্ন। প্রতিটি অর্ডার নম্বরকে মৌলিক সংখ্যার গুণফলে ভেঙে একটি “আঙুলের ছাপ” বানানো হবে। দাবি: ২ বা তার বেশি প্রতিটি পূর্ণসংখ্যা মৌলিক সংখ্যার গুণফল। সাধারণ induction-এ চেষ্টা করি। ধরুন জানি ৫৯ মৌলিক সংখ্যার গুণফল (৫৯ নিজেই মৌলিক)। এখন ৬০ নিয়ে কী বলা যায়? ৬০ = ৬ × ১০. এখানে লাগে ৬ আর ১০-এর গুণনীয়ক, ৫৯-এর নয়। P(59) জেনে P(60) সম্পর্কে কিছুই পাওয়া যায় না।

৬০-এর জন্য দরকার ছিল ৬ আর ১০, দুটোই ৬০-এর চেয়ে ছোট। যদি এমন একটি প্রমাণ-কাঠামো থাকে যেখানে P(60) প্রমাণের সময় ২ থেকে ৫৯ পর্যন্ত সব মানে দাবিটি সত্য ধরে নেওয়া যায়, তাহলে কাজ সহজ। সেটিই strong induction.

২ · Strong induction — নীতি, ছাঁচ আর কেন বৈধ

একে complete induction বা second principle of induction-ও বলে। পার্থক্য শুধু inductive step-এ: সাধারণ mathematical induction-এ হাতে থাকে শুধু P(k); এখানে P(b) থেকে P(k) পর্যন্ত সবগুলো। প্রথম অংশটিকে বলে basis step.

নিচের ছবিতে পার্থক্যটি দেখুন। ওপরের সারিতে প্রতিটি সংখ্যা শুধু ঠিক আগেরটির ওপর দাঁড়ায়। নিচের সারিতে ৮-এর প্রমাণ দাঁড়িয়েছে ২ আর ৪-এর ওপর (৮ = ২ × ৪), যদিও ২ থেকে ৭ পর্যন্ত সবাই হাতের কাছে ছিল।

কেন বৈধ — সাধারণ induction থেকে প্রমাণ

প্রমাণ: ধরি strong induction-এর দুই শর্ত পূর্ণ হয়েছে (এক basis b-এর ক্ষেত্রে; কয়েকটি basis হলে একই যুক্তি)। নতুন একটি দাবি বানাই: Q(n) = P(b) ∧ P(b + 1) ∧ … ∧ P(n), অর্থাৎ “b থেকে n পর্যন্ত সবগুলোতে P সত্য”।

1. Q(b) = P(b), যা basis অনুযায়ী সত্য। তাই Q-এর basis পূর্ণ।
2. ধরি কোনো k ≥ b-তে Q(k) সত্য, অর্থাৎ P(b), …, P(k) সব সত্য (সাধারণ induction-এর hypothesis).
3. Strong induction-এর ধাপ ২ বলে [P(b) ∧ … ∧ P(k)] → P(k + 1); ধাপ ২-এর তথ্যের সঙ্গে modus ponens দিয়ে P(k + 1) সত্য।
4. Q(k) আর P(k + 1) একসঙ্গে মানে Q(k + 1) (conjunction-এর সংজ্ঞা)। তাই Q(k) → Q(k + 1).
5. সাধারণ induction দিয়ে সব n ≥ b-তে Q(n) সত্য; আর Q(n) সত্য হলে তার শেষ অংশ P(n)-ও সত্য (simplification). ∎

অর্থাৎ strong induction আসলে নতুন কোনো স্বীকার্য নয়; এটি সাধারণ induction, শুধু দাবিটিকে “এখন পর্যন্ত সবগুলো” আকারে শক্ত করে লেখা। উল্টো দিকটি আরও সহজ: সাধারণ induction-এর প্রতিটি প্রমাণ strong induction-এরও প্রমাণ, কারণ hypothesis-এর শুধু শেষ অংশ P(k) ব্যবহার করলেই চলে। “Strong” নামটি তাই একটু বিভ্রান্তিকর: শক্তিশালী হলো hypothesis, প্রমাণ-পদ্ধতির ক্ষমতা একই।

৩ · প্রতিটি n ≥ 2 মৌলিক সংখ্যার গুণফল

একটি মৌলিক সংখ্যা (prime) হলো ১-এর চেয়ে বড় পূর্ণসংখ্যা, যার ধনাত্মক ভাজক শুধু ১ আর সংখ্যাটি নিজে। ১-এর চেয়ে বড় যে সংখ্যা মৌলিক নয়, তাকে বলে যৌগিক সংখ্যা (composite): তাকে n = a · b লেখা যায়, যেখানে 1 < a, b < n. একটিমাত্র মৌলিক সংখ্যাকেও “একটি মৌলিকের গুণফল” ধরা হয়।

প্রমাণ (strong induction, n-এর ওপর): P(n) = “n মৌলিক সংখ্যার গুণফল”।

1. Basis: n = 2. ২-এর ধনাত্মক ভাজক শুধু ১ আর ২, তাই ২ মৌলিক; এটি নিজেই একটি মৌলিকের গুণফল। P(2) সত্য।
2. Hypothesis: কোনো k ≥ 2-এর জন্য ধরি P(2), P(3), …, P(k) সব সত্য। দেখাতে হবে P(k + 1).
3. ক্ষেত্র ১, k + 1 মৌলিক: তাহলে k + 1 নিজেই একটি মৌলিকের গুণফল। P(k + 1) সত্য।
4. ক্ষেত্র ২, k + 1 যৌগিক: সংজ্ঞা অনুযায়ী k + 1 = a · b, যেখানে 1 < a < k + 1 আর 1 < b < k + 1. অর্থাৎ 2 ≤ a ≤ k আর 2 ≤ b ≤ k.
5. a আর b দুটোই hypothesis-এর পরিসরে (২ থেকে k), তাই P(a) আর P(b) সত্য: a = p₁⋯p_r, b = q₁⋯q_s, সবগুলো মৌলিক।
6. তাহলে k + 1 = p₁⋯p_r · q₁⋯q_s, মৌলিক সংখ্যার গুণফল। P(k + 1) সত্য।
7. দুই ক্ষেত্র সব সম্ভাবনা ঢাকে (১-এর চেয়ে বড় প্রতিটি সংখ্যা মৌলিক অথবা যৌগিক)। Strong induction-এ সব n ≥ 2-তে P(n) সত্য। ∎

ধাপ ৫-ই মূল জায়গা: a আর b কত, আমরা জানি না, শুধু জানি তারা k + 1-এর চেয়ে ছোট আর অন্তত ২। সাধারণ induction-এ শুধু P(k) হাতে থাকত, যা এখানে অকেজো। এবার প্রমাণটিকে ৬০-এর ওপর চালিয়ে দেখুন; প্রমাণের প্রতিটি ধাপ আসলে একটি recursive algorithm-এর ধাপ।

160 = 6 × 102 6 = 2 × 3310 = 2 × 5460 = 2·3·2·5560 = 4 × 15

উপপাদ্য ৩.১ হলো fundamental theorem of arithmetic-এর অস্তিত্বের (existence) অংশ। পূর্ণ উপপাদ্য বলে, ক্রম বাদ দিলে ভাঙনটি অনন্য; সেটির জন্য Euclid-এর lemma (“p মৌলিক আর p ∣ ab হলে p ∣ a অথবা p ∣ b”) লাগে, যা পর্ব ২০ “বিভাজ্যতা আর মৌলিক সংখ্যা — division algorithm আর unique factorization”-এর বিষয়। এখানে ∣ চিহ্নের অর্থ “ভাগ করে”।

৪ · ৩ আর ৫ টাকার টিকিট — আগে Python, তারপর দুই প্রমাণ

বাজারঘর ছোট পার্সেলে ডাক-টিকিট লাগায়। গুদামে শুধু ৩ টাকা আর ৫ টাকার টিকিট আছে, যত খুশি। কোন কোন মাশুল ঠিক ঠিক মেটানো যায়? যেমন ৮ = ৩ + ৫, কিন্তু ৭? প্রমাণ লেখার আগে ছোট মানগুলো দেখে নিই। গণিতবিদরাও এভাবেই শুরু করেন: হিসাব করে প্যাটার্ন দেখা, তারপর অনুমান (conjecture), তারপর প্রমাণ।

নিচের ব্লকে ok[n] সত্য হয়, যদি n − a বা n − b আগেই সত্য হয়ে থাকে। খেয়াল করুন: n-এর উত্তর ছোট মানের উত্তর থেকে আসছে, ঠিক strong induction-এর মতো। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from math import gcd

def representable(a, b, limit):
    # ok[n] = n টাকা কি a আর b টাকার টিকিটে ঠিক ঠিক হয়?
    ok = [False] * (limit + 1)
    ok[0] = True                      # কোনো টিকিট নয়: 0 টাকা
    for n in range(1, limit + 1):
        ok[n] = (n >= a and ok[n - a]) or (n >= b and ok[n - b])
    return ok

ok = representable(3, 5, 30)
print("3 and 5, not possible in 1..30:", [n for n in range(1, 31) if not ok[n]])
for n in range(8, 17):
    j = next(j for j in range(n // 5 + 1) if (n - 5 * j) % 3 == 0)
    print(f"  {n:2} = 3 x {(n - 5 * j) // 3} + 5 x {j}")

print("a  b  largest-bad  ab-a-b  #bad  (a-1)(b-1)/2")
for a, b in [(3, 5), (4, 5), (5, 7), (4, 9), (6, 9)]:
    ok = representable(a, b, 200)
    bad = [n for n in range(1, 201) if not ok[n]]
    if gcd(a, b) > 1:
        print(f"{a}  {b}  gcd = {gcd(a, b)}: only multiples of {gcd(a, b)}, no largest")
        continue
    print(f"{a}  {b}  {max(bad):6}  {a*b-a-b:10}  {len(bad):4}  {(a-1)*(b-1)//2:6}")

3 and 5, not possible in 1..30: [1, 2, 4, 7]
   8 = 3 x 1 + 5 x 1
   9 = 3 x 3 + 5 x 0
  10 = 3 x 0 + 5 x 2
  11 = 3 x 2 + 5 x 1
  12 = 3 x 4 + 5 x 0
  13 = 3 x 1 + 5 x 2
  14 = 3 x 3 + 5 x 1
  15 = 3 x 5 + 5 x 0
  16 = 3 x 2 + 5 x 2
a  b  largest-bad  ab-a-b  #bad  (a-1)(b-1)/2
3  5       7           7     4       4
4  5      11          11     6       6
5  7      23          23    12      12
4  9      23          23    12      12
6  9  gcd = 3: only multiples of 3, no largest

প্রায় ২০০ পর্যন্ত যাচাই প্রমাণ নয়; ২০১ টাকায় কী হবে? এবার দুইভাবে প্রমাণ করি।

প্রমাণ ১ (সাধারণ induction):

1. Basis: 8 = 3 · 1 + 5 · 1.
2. Hypothesis: কোনো k ≥ 8-এর জন্য k = 3x + 5y, x, y ≥ 0.
3. ক্ষেত্র y ≥ 1 (অন্তত একটি ৫ টাকার টিকিট আছে): একটি ৫ সরিয়ে দুটি ৩ বসাই: k + 1 = 3(x + 2) + 5(y − 1); কারণ −5 + 6 = +1, আর y − 1 ≥ 0.
4. ক্ষেত্র y = 0 (সব ৩ টাকার): তখন k = 3x ≥ 8, তাই x ≥ 3 (কারণ 3 · 2 = 6 < 8). তিনটি ৩ সরিয়ে দুটি ৫ বসাই: k + 1 = 3(x − 3) + 5 · 2; কারণ −9 + 10 = +1.
5. দুই ক্ষেত্রেই k + 1 = 3x′ + 5y′, x′, y′ ≥ 0. সাধারণ induction-এ সব n ≥ 8-এ দাবি সত্য। ∎

প্রমাণ ১ সুন্দর, কিন্তু চালাকি লাগে (“কোন টিকিট বদলাব?”)। প্রমাণ ২ অনেক সরাসরি: প্রতিটি অঙ্ক তিন টাকা কম অঙ্কের সঙ্গে একটি ৩ টাকার টিকিট।

প্রমাণ ২ (strong induction):

1. Basis (তিনটি): 8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5.
2. Hypothesis: কোনো k ≥ 10-এর জন্য ৮ থেকে k পর্যন্ত প্রতিটি অঙ্ক বানানো যায়।
3. ধাপ: k + 1 ≥ 11, তাই (k + 1) − 3 = k − 2 ≥ 8; আবার k − 2 ≤ k. অর্থাৎ k − 2 hypothesis-এর পরিসরে, তাকে বানানো যায়।
4. সেই টিকিটগুলোর সঙ্গে একটি ৩ টাকার টিকিট যোগ করলে k + 1. ∎

1P(n): n = 3x + 5y2basis: 8 = 3 + 53basis: 9 = 3 + 3 + 34basis: 10 = 5 + 55step: n = (n − 3) + 3

প্রমাণ ২-কে সাধারণ induction-এ রূপান্তর করা যায়, উপপাদ্য ২.১-এর মতো: Q(n) = “n, n − 1, n − 2 তিনটিই বানানো যায়”। কিন্তু strong induction-এ চিন্তাটি অনেক পরিষ্কার।

৫ · কত basis লাগবে — আর একটি ভুল প্রমাণ

Strong induction-এর সবচেয়ে সাধারণ ভুল basis কম রাখা। নিয়মটি সহজ: ধাপে P(k + 1) প্রমাণের সময় যে ছোট মানগুলো ব্যবহার করছেন, প্রতিটি k-এর জন্য সেগুলো যেন দাবির পরিসরে (≥ b) থাকে। যেসব k + 1-এ ধাপটি পরিসরের বাইরে চলে যায়, সেগুলো আলাদা basis case.

এবার একটি বিখ্যাত ভুল “প্রমাণ”। খুঁজে দেখুন কোথায় ভাঙছে, তারপর নিচে পড়ুন।

ভুলটি: ধাপে a^k−1 ব্যবহার হয়েছে, অর্থাৎ P(k − 1). k = 0 হলে (k + 1 = 1 প্রমাণের সময়) k − 1 = −1, যা দাবির পরিসর n ≥ 0-এর বাইরে; hypothesis সেখানে কিছুই বলে না। আসলে a⁻¹ = 1/a, যা সাধারণত ১ নয়। ধাপ শুধু k ≥ 1-এ বৈধ, তাই দুটি basis লাগত: a⁰ = 1 আর a¹ = 1. দ্বিতীয়টি মিথ্যা (a = 2 হলে a¹ = 2), তাই পুরো দাবিই ভেঙে পড়ে। এক লাইনের এই ফাঁক পর্ব ১০-এর “সব ঘোড়া একই রঙের” ভুল প্রমাণের আত্মীয়: সেখানেও ধাপটি ঠিক একটি ছোট মানে (n = 1 থেকে 2) খাটে না।

৬ · কাঠির খেলা — জেতার কৌশলের প্রমাণ

বাজারঘরের অফিসে চা-বিরতিতে একটি খেলা চলে। টেবিলে n-টি দেশলাই কাঠি। দুজন পালা করে ১, ২ বা ৩টি কাঠি তোলেন। যিনি শেষ কাঠিটি তোলেন, তিনি জেতেন। প্রশ্ন: কোন n-এ প্রথম খেলোয়াড় নিশ্চিত জিততে পারেন, প্রতিপক্ষ যত ভালোই খেলুক? এমন নিশ্চিত পরিকল্পনাকে বলে winning strategy. খেলাটি Nim পরিবারের একটি সরল সদস্য।

আবার আগে হিসাব। একটি অবস্থান (n কাঠি বাকি) “জেতা” (W), যদি অন্তত একটি চাল প্রতিপক্ষকে “হারা” (L) অবস্থানে পাঠায়; আর “হারা”, যদি প্রতিটি চাল প্রতিপক্ষকে জেতা অবস্থানে পাঠায়। ০ কাঠি L: যাঁর পালা, তাঁর আগেরজন শেষ কাঠি তুলে জিতে গেছেন। এই সংজ্ঞাটিই একটি ছোট game tree-এর হিসাব, আর n-এর উত্তর আসে ছোট সব n-এর উত্তর থেকে।

from functools import lru_cache

MOVES = (1, 2, 3)

@lru_cache(maxsize=None)
def wins(n):
    # n কাঠি বাকি; যাঁর পালা, তিনি কি নিশ্চিত জিততে পারেন?
    # এমন একটি চাল খুঁজি, যার পর প্রতিপক্ষ হারা অবস্থানে পড়েন
    return any(not wins(n - m) for m in MOVES if m <= n)

def good_moves(n):
    return [m for m in MOVES if m <= n and not wins(n - m)]

print("n  :", " ".join(f"{n:2}" for n in range(17)))
print("W/L:", " ".join(" W" if wins(n) else " L" for n in range(17)))
print("losing n up to 60:", [n for n in range(61) if not wins(n)])
print("wins(n) == (n % 4 != 0) for all n <= 500:",
      all(wins(n) == (n % 4 != 0) for n in range(501)))
for n in (15, 22, 4):
    print(f"n = {n}: winning first moves {good_moves(n)}")

n  :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
W/L:  L  W  W  W  L  W  W  W  L  W  W  W  L  W  W  W  L
losing n up to 60: [0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60]
wins(n) == (n % 4 != 0) for all n <= 500: True
n = 15: winning first moves [3]
n = 22: winning first moves [2]
n = 4: winning first moves []

প্রমাণ (strong induction, n-এর ওপর): P(n) = উপপাদ্যের দাবি, n কাঠির জন্য।

1. Basis, n = 0: 4 ∣ 0. যাঁর পালা তিনি কোনো চাল দিতে পারেন না; শেষ কাঠি আগেরজন তুলেছেন, তাই তিনি হেরেছেন। P(0) সত্য।
2. Hypothesis: কোনো n ≥ 1-এর জন্য ধরি 0 ≤ j < n সব j-এ P(j) সত্য।
3. ক্ষেত্র 4 ∤ n: r = n mod 4 ∈ {1, 2, 3}, আর r ≤ n, তাই r-টি কাঠি তোলা বৈধ চাল। বাকি থাকে n − r, যা ৪-এর গুণিতক আর n-এর চেয়ে ছোট। Hypothesis P(n − r) অনুযায়ী এখন যাঁর পালা (প্রতিপক্ষ), তিনি হারবেন। তাই n-এ যাঁর পালা, তিনি জেতেন।
4. ক্ষেত্র 4 ∣ n (তাই n ≥ 4): যেকোনো চালে m ∈ {1, 2, 3} কাঠি তুললে বাকি n − m, যা ৪-এর গুণিতক নয় (৪ দিয়ে ভাগশেষ 4 − m), আর 0 ≤ n − m < n. Hypothesis P(n − m) অনুযায়ী প্রতিপক্ষ সেখান থেকে নিশ্চিত জিততে পারেন। তাই n-এ যাঁর পালা, তিনি হারবেন।
5. দুই ক্ষেত্রেই P(n) সত্য; strong induction-এ সব n ≥ 0-এ P(n) সত্য। ∎

ধাপ ৩ আর ৪-এ লাগল P(n − 1), P(n − 2) বা P(n − 3), কোনটি তা চালের ওপর নির্ভর করে; তাই strong hypothesis স্বাভাবিক। Basis একটিই যথেষ্ট, কারণ n ≥ 1-এ প্রতিটি বৈধ চাল 0 বা তার বেশি কাঠি রাখে, পরিসরের বাইরে যায় না। খেলার এই ধরনের বিশ্লেষণ, আর বড় খেলায় minimax, AI-এর ভিত্তি আর Python for AI কোর্সের পর্ব ৪২-এ আছে।

৭ · Well-ordering principle আর induction-এর সমতুল্যতা

এবার একই শক্তিকে অন্য দিক থেকে দেখি। ক্লাসের রোল নম্বরের তালিকায় যত জনই থাকুক, সবচেয়ে ছোট রোল নম্বর একটি আছেই। স্বাভাবিক সংখ্যার এই সাধারণ ধর্মটির নাম:

Well-ordering principle সব সংখ্যা-সেটে খাটে না। পূর্ণসংখ্যা ℤ-এ {…, −3, −2, −1}-এর কোনো ক্ষুদ্রতম নেই। ধনাত্মক মূলদ সংখ্যার সেটে 1, 1/2, 1/3, … ক্রমশ ছোট হয়, কিন্তু ক্ষুদ্রতম কেউ নেই (যেকোনো q > 0-এর চেয়ে q/2 ছোট)। তবে {n ∈ ℤ : n ≥ −5}-এর মতো নিচে আটকানো পূর্ণসংখ্যার সেটে খাটে, কারণ সবাইকে ৫ যোগ করে ℕ-এ সরানো যায়।

(ক)-এর প্রমাণ (contradiction): ধরি P(0) সত্য আর প্রতিটি k-এ P(k) → P(k + 1), কিন্তু তবুও কোনো n-এ P(n) মিথ্যা।

1. S = {n ∈ ℕ : P(n) মিথ্যা}. ধারণা অনুযায়ী S অশূন্য।
2. Well-ordering অনুযায়ী S-এর ক্ষুদ্রতম উপাদান m আছে।
3. P(0) সত্য, তাই 0 ∉ S, অর্থাৎ m ≠ 0; তাই m ≥ 1 আর m − 1 ∈ ℕ.
4. m − 1 < m, আর m ক্ষুদ্রতম, তাই m − 1 ∉ S: P(m − 1) সত্য।
5. P(m − 1) → P(m) থেকে (modus ponens) P(m) সত্য, অথচ m ∈ S মানে P(m) মিথ্যা। বিরোধ। তাই S শূন্য, সব n-এ P(n) সত্য। ∎

(খ)-এর প্রমাণ: ধরি S ⊆ ℕ-এর কোনো ক্ষুদ্রতম উপাদান নেই; দেখাব S শূন্য। P(n) = “n ∉ S”.

1. Strong hypothesis: 0 ≤ j < n সব j-এ j ∉ S (n = 0-এ এই শর্ত ফাঁকা)।
2. যদি n ∈ S হতো, তাহলে n-এর চেয়ে ছোট কেউ S-এ নেই (ধাপ ১), অর্থাৎ n হতো S-এর ক্ষুদ্রতম। কিন্তু S-এর ক্ষুদ্রতম নেই। তাই n ∉ S: P(n) সত্য।
3. ধাপ ১-২ সব n-এ খাটে (n = 0-ও, তাই আলাদা basis লাগে না)। Strong induction-এ সব n-এ n ∉ S, অর্থাৎ S = ∅. Contrapositive: S অশূন্য হলে তার ক্ষুদ্রতম উপাদান আছে। ∎

উপপাদ্য ২.১ (সাধারণ ⟹ strong) মিলিয়ে একটি চক্র পূর্ণ হলো: well-ordering ⟹ সাধারণ induction ⟹ strong induction ⟹ well-ordering. তিনটি আসলে একই সত্যের তিন রূপ। এটি একটি প্রমাণের রূপরেখা: পুরো কঠোরতায় ℕ-এর বাকি মৌলিক ধর্ম (যেমন প্রতিটি ধনাত্মক সংখ্যার আগে একটি সংখ্যা আছে) মেনে নিতে হয়, যা Peano-র স্বীকার্যে লেখা থাকে।

৮ · Well-ordering সরাসরি — division algorithm আর minimal counterexample

কখনো কখনো induction-এর বদলে সরাসরি “সবচেয়ে ছোটটি নিন” বলা অনেক স্বাভাবিক। প্রথম উদাহরণ ভাগশেষ। বাজারঘরে ৪৫টি ডিম ৭টি করে ট্রেতে সাজালে ৬টি ট্রে ভরে, ৩টি ডিম বাকি থাকে: 45 = 7 · 6 + 3. এমন ভাগফল আর ভাগশেষ সবসময় আছে কেন?

প্রমাণ (well-ordering):

1. S = {n − dq : q ∈ ℤ, আর n − dq ≥ 0}. এটি ℕ-এর উপসেট।
2. S অশূন্য: q = −|n| নিলে n − dq = n + d|n| ≥ n + |n| ≥ 0, কারণ d ≥ 1.
3. Well-ordering অনুযায়ী S-এর ক্ষুদ্রতম উপাদান r আছে; কোনো q-এর জন্য r = n − dq, তাই n = dq + r, আর r ≥ 0.
4. ধরি r ≥ d. তাহলে r − d = n − d(q + 1) ≥ 0, তাই r − d ∈ S, অথচ r − d < r (কারণ d > 0). এটি r-এর ক্ষুদ্রতমতার বিরোধী।
5. তাই r < d. অর্থাৎ 0 ≤ r < d. ∎

৪৫ আর ৭-এ: S = {45, 38, 31, 24, 17, 10, 3} (q = 0, 1, …, 6), ক্ষুদ্রতম ৩, q = 6. ঋণাত্মক n-এও খাটে: −17 = 5 · (−4) + 3. Python-এর divmod(-17, 5) ঠিক এই (-4, 3) দেয়, কারণ ধনাত্মক d-এ Python-এর ভাগশেষ কখনো ঋণাত্মক হয় না। এমন q আর r যে একটিই, সেই প্রমাণ পর্ব ২০-এ। এর division algorithm নাম ঐতিহ্যগত; এটি আসলে একটি উপপাদ্য।

Minimal counterexample কৌশল

সাধারণ ছাঁচ: “সব n ≥ b-তে P(n)” প্রমাণ করতে ধরে নিন এটি মিথ্যা। তাহলে ব্যতিক্রমের সেট অশূন্য, তাই well-ordering অনুযায়ী একটি ক্ষুদ্রতম ব্যতিক্রম m আছে। এবার m থেকে আরও ছোট একটি ব্যতিক্রম বানান, বা m-এর চেয়ে ছোট সবাই ঠিক বলে m-ও ঠিক দেখান। দুটোই বিরোধ। এর নাম minimal counterexample. নিচের stepper-এ একই যুক্তি একটি সত্য আর একটি মিথ্যা দাবিতে চালানো হলো।

1S = ব্যতিক্রম, m = min S2ছোট মান হাতে যাচাই3m − 3 ∉ S ⟹ m ∉ S

আরেকটি minimal counterexample: √2-এর অমূলদতা

পর্ব ০৮ “প্রমাণের পদ্ধতি — direct, contrapositive আর contradiction”-এ √2-এর অমূলদতার একটি প্রমাণ আছে, জোড়-বিজোড় যুক্তি দিয়ে। Well-ordering দিয়ে আরেকটি, একেবারে ভিন্ন প্রমাণ:

1. ধরি √2 মূলদ। তাহলে S = {b ∈ ℤ, b ≥ 1 : b√2 একটি পূর্ণসংখ্যা} অশূন্য। এর ক্ষুদ্রতম উপাদান b নিই, আর a = b√2 (পূর্ণসংখ্যা)।
2. c = a − b = b(√2 − 1) নিই। এটি পূর্ণসংখ্যা। 1 < √2 < 2, তাই 0 < √2 − 1 < 1, অর্থাৎ 0 < c < b; c ধনাত্মক পূর্ণসংখ্যা, তাই c ≥ 1.
3. c√2 = b√2 · √2 − b√2 = 2b − a, যা পূর্ণসংখ্যা। তাই c ∈ S.
4. c ∈ S আর c < b, অথচ b ছিল S-এর ক্ষুদ্রতম। বিরোধ। তাই √2 অমূলদ। ∎

খেয়াল করুন, ক্ষুদ্রতম ব্যতিক্রম থেকে আরও ছোট একটি ব্যতিক্রম বানানো হলো। এই ধাঁচের প্রমাণকে ঐতিহাসিকভাবে infinite descent বলে: একটি ব্যতিক্রম থাকলে অসীম সংখ্যক ক্রমশ ছোট স্বাভাবিক সংখ্যা থাকত, যা অসম্ভব।

প্রমাণ খোঁজার আগে প্রথম ব্যতিক্রম খুঁজে দেখা সবসময় বুদ্ধিমানের কাজ। নিচের ব্লক কয়েকটি দাবির ক্ষুদ্রতম ব্যতিক্রম খোঁজে, ছোট থেকে বড় ক্রমে: well-ordering-এর হাতে-কলমে রূপ।

def is_prime(n):
    return n > 1 and all(n % d for d in range(2, int(n ** 0.5) + 1))

def smallest_counterexample(claim, start, limit):
    # ছোট থেকে বড়: প্রথম যেখানে দাবি ভাঙে, সেটিই ক্ষুদ্রতম ব্যতিক্রম
    for n in range(start, limit + 1):
        if not claim(n):
            return n
    return None

def stamps(n):          # n টাকা কি 3 আর 5 টাকার টিকিটে হয়?
    return any((n - 5 * j) % 3 == 0 for j in range(n // 5 + 1))

def odd_composite(n):   # বিজোড় যৌগিক n = মৌলিক + 2k² ?
    if n % 2 == 0 or is_prime(n):
        return True     # দাবিটি শুধু বিজোড় যৌগিক সংখ্যা নিয়ে
    return any(is_prime(n - 2 * k * k) for k in range(1, int((n / 2) ** 0.5) + 1))

claims = [
    ("stamps 3, 5 for n >= 8", stamps, 8, 2000),
    ("stamps 3, 5 for n >= 5", stamps, 5, 2000),
    ("n*n + n + 41 is prime", lambda n: is_prime(n * n + n + 41), 0, 2000),
    ("odd composite = p + 2k^2", odd_composite, 3, 10000),
]
for name, claim, start, limit in claims:
    m = smallest_counterexample(claim, start, limit)
    print(f"{name:26}", f"none up to {limit}" if m is None else f"smallest counterexample {m}")
print("5777 =", " = ".join(f"{a}*{b}" for a in range(2, 76) for b in [5777 // a] if a * b == 5777))
print("5777 - 2k^2 composite for every k = 1..53:",
      all(not is_prime(5777 - 2 * k * k) for k in range(1, 54)))

stamps 3, 5 for n >= 8     none up to 2000
stamps 3, 5 for n >= 5     smallest counterexample 7
n*n + n + 41 is prime      smallest counterexample 40
odd composite = p + 2k^2   smallest counterexample 5777
5777 = 53*109
5777 - 2k^2 composite for every k = 1..53: True

৯ · Algorithm বিশ্লেষণে strong induction

Recursive algorithm প্রায় সবসময় নিজেকে ছোট কিন্তু “ঠিক এক কম নয়” এমন ইনপুটে ডাকে: binary search অর্ধেকে, merge sort দুই অর্ধেকে, Euclid-এর gcd ভাগশেষে। তাই এদের চলার সময়ের recurrence প্রমাণে strong induction স্বাভাবিক। Recurrence সমাধানের algorithm-কেন্দ্রিক পদ্ধতি (unrolling, recursion tree, substitution) DSA কোর্সের পর্ব ০৮-এ আছে; এখানে শুধু প্রমাণের যুক্তিটি দেখি।

Sorted তালিকায় n-টি আইটেম থাকলে binary search মাঝের আইটেম দেখে, তারপর বাকি দুই ভাগের একটিতে খোঁজে। বড় ভাগে ⌊n/2⌋টি আইটেম থাকে (⌊x⌋ মানে x-এর চেয়ে বড় নয় এমন বৃহত্তম পূর্ণসংখ্যা)। তাই সবচেয়ে খারাপ ক্ষেত্রে দেখার সংখ্যা T(1) = 1, আর n ≥ 2-এ T(n) = T(⌊n/2⌋) + 1.

প্রমাণ (strong induction):

1. Basis: T(1) = 1 = ⌊log₂ 1⌋ + 1 = 0 + 1.
2. Hypothesis: কোনো n ≥ 2-এর জন্য 1 ≤ j < n সব j-এ T(j) = ⌊log₂ j⌋ + 1.
3. e = ⌊log₂ n⌋ ধরি; সংজ্ঞা অনুযায়ী 2^e ≤ n < 2^e+1, আর n ≥ 2 বলে e ≥ 1.
4. ২ দিয়ে ভাগ করে 2^e−1 ≤ n/2 < 2^e. 2^e−1 পূর্ণসংখ্যা, তাই floor নিলেও 2^e−1 ≤ ⌊n/2⌋ < 2^e; অর্থাৎ ⌊log₂ ⌊n/2⌋⌋ = e − 1.
5. 1 ≤ ⌊n/2⌋ < n, তাই hypothesis খাটে: T(⌊n/2⌋) = (e − 1) + 1 = e.
6. T(n) = T(⌊n/2⌋) + 1 = e + 1 = ⌊log₂ n⌋ + 1. ∎

ধাপ ৫-এ ⌊n/2⌋ সাধারণত n − 1 থেকে অনেক দূরে, তাই P(n − 1) এখানে অকেজো। একই কাঠামোয় merge sort-এর সবচেয়ে খারাপ ক্ষেত্রের তুলনা-সংখ্যা M(1) = 0, M(n) = M(⌈n/2⌉) + M(⌊n/2⌋) + n − 1-এর জন্য বন্ধ সূত্র M(n) = n⌈log₂ n⌉ − 2^{⌈log₂ n⌉} + 1 প্রমাণ করা যায়। প্রমাণের আগে Python-এ যাচাই:

N = 4096
T = [0] * (N + 1)
M = [0] * (N + 1)
T[1], M[1] = 1, 0
for n in range(2, N + 1):
    T[n] = T[n // 2] + 1                        # binary search: এক তুলনা + বড় অর্ধেক
    M[n] = M[(n + 1) // 2] + M[n // 2] + n - 1  # merge sort-এর সবচেয়ে খারাপ ক্ষেত্র

def clog(n):            # ceil(log2 n), float ছাড়াই
    return (n - 1).bit_length()

print("T(n) == floor(log2 n) + 1 for 1..4096:",
      all(T[n] == n.bit_length() for n in range(1, N + 1)))
print("M(n) == n*clog(n) - 2**clog(n) + 1 for 1..4096:",
      all(M[n] == n * clog(n) - 2 ** clog(n) + 1 for n in range(1, N + 1)))
print(" n    T(n)  M(n)  n*clog(n)")
for n in (1, 2, 3, 7, 8, 100, 1000, 4096):
    print(f"{n:4}  {T[n]:4}  {M[n]:5}  {n * clog(n):6}")

T(n) == floor(log2 n) + 1 for 1..4096: True
M(n) == n*clog(n) - 2**clog(n) + 1 for 1..4096: True
 n    T(n)  M(n)  n*clog(n)
   1     1      0       0
   2     2      1       2
   3     2      3       6
   7     3     14      21
   8     4     17      24
 100     7    573     700
1000    10   8977   10000
4096    13  45057   49152

আরেকটি পরিচিত উদাহরণ: প্রতিটি n ≥ 1-এর একটি binary রূপ আছে (২-এর ভিন্ন ভিন্ন ঘাতের যোগফল)। Strong induction-এ: n = 1 = 2⁰. n ≥ 2 হলে n = 2⌊n/2⌋ + (n mod 2); hypothesis থেকে ⌊n/2⌋-এর binary রূপ আছে, সব ঘাত এক করে বাড়ালে 2⌊n/2⌋-এর রূপ, আর n বিজোড় হলে সঙ্গে 2⁰ (যা তখন তালিকায় নেই, কারণ বাকি ঘাত সব ≥ 1). Python-এর bin(n) ঠিক এই recursion-ই করে, উল্টো দিক থেকে। Recursive function কীভাবে নিজেকে ডাকে, Python প্রোগ্রামিং কোর্সের পর্ব ১৩-এ আছে; algorithm-এর সঠিকতার প্রমাণ DSA কোর্সের পর্ব ০৩-এ।

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

AI সহকারী induction প্রমাণ খুব আত্মবিশ্বাসের সঙ্গে লেখে, আর strong induction-এর ভুলগুলো চোখে পড়ে কম, কারণ প্রমাণ দেখতে ছোট আর পরিষ্কার। যে ভুলগুলো বেশি দেখা যায়:

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

• P(n) আর শুরুর মান b স্পষ্ট; দাবির পরিসর প্রশ্নের সঙ্গে মেলে
• ধাপে ব্যবহৃত প্রতিটি মান b আর k-এর মধ্যে, সবচেয়ে ছোট k-এও
• Basis case-এর সংখ্যা ধাপের “পেছনে যাওয়ার দূরত্ব” অনুযায়ী
• প্রতিটি ক্ষেত্র-বিভাগ (মৌলিক/যৌগিক, ৪ ∣ n কি না) সব সম্ভাবনা ঢাকে
• Python-এ ছোট মানে দাবি আর প্রতিটি basis হিসাব নিজে যাচাই করেছি
• উল্লেখ করা উপপাদ্যের শর্ত (যেমন gcd = 1) একটি বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি