Mathematical induction — এক ধাপ থেকে অসীম পর্যন্ত

১ · ডমিনোর সারি — induction-এর নীতি আর কেন তা বৈধ

বাজারঘরের গুদামে প্রতিটি অর্ডারের একটি ক্রমিক id থাকে: 1, 2, 3, …. ধরুন দাবি করা হলো, “প্রথম n টি অর্ডারের id-এর যোগফল n(n+1)/2”. n = 1, 2, 3 বসিয়ে মিলিয়ে দেখা সহজ, কিন্তু অর্ডার তো অসীম পর্যন্ত চলতে পারে। প্রতিটি n আলাদা করে যাচাই করা কখনো শেষ হবে না। পর্ব ০১-এ দেখেছেন, n² + n + 41 প্রথম ৪০টি n-এ মৌলিক হয়েও n = 40-এ ভেঙে পড়ে। তাই অসীম সংখ্যক দাবির জন্য দরকার এমন একটি যুক্তি, যা একবারে সব n ঢাকে।

Mathematical induction-এর বাংলা নাম গাণিতিক আরোহ। নামে “induction” থাকলেও এটি বিজ্ঞানের “অনেক উদাহরণ দেখে সাধারণ সিদ্ধান্ত” নয়; এটি পুরোপুরি নিশ্চিত, deductive একটি প্রমাণ। Inductive step-এ P(k) সত্য ধরে নেওয়া হয়; এই অনুমানকে বলে inductive hypothesis. এটি “সব k-এর জন্য P(k) সত্য” ধরে নেওয়া নয়, যা হতো উপসংহারকেই ধরে নেওয়া। এটি শুধু একটি conditional P(k) → P(k+1) প্রমাণের সাধারণ কৌশল: শর্ত সত্য ধরে ফল দেখানো (পর্ব ০৮-এর direct proof).

নীতিটি কেন বৈধ — well-ordering থেকে প্রমাণ

স্বাভাবিক সংখ্যার একটি মৌলিক ধর্ম হলো well-ordering principle: ধনাত্মক পূর্ণসংখ্যার প্রতিটি অশূন্য উপসেটে একটি সবচেয়ে ছোট সদস্য থাকে। (বাস্তব সংখ্যায় এটি খাটে না: শূন্যের চেয়ে বড় বাস্তব সংখ্যার কোনো সবচেয়ে ছোটটি নেই।)

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

1. S = {n ≥ 1 : P(n) মিথ্যা} সেটটি অশূন্য — ধরে নেওয়া অনুমান অনুযায়ী।
2. Well-ordering অনুযায়ী S-এর একটি সবচেয়ে ছোট সদস্য m আছে।
3. m ≠ 1, কারণ P(1) সত্য (basis). তাই m ≥ 2, অর্থাৎ m − 1 ≥ 1.
4. m − 1 < m আর m সবচেয়ে ছোট, তাই m − 1 ∉ S; অর্থাৎ P(m − 1) সত্য।
5. Inductive step-এ k = m − 1 বসালে P(m − 1) → P(m); ধাপ ৪-এর সঙ্গে modus ponens দিয়ে P(m) সত্য।
6. কিন্তু m ∈ S মানে P(m) মিথ্যা। বিরোধ; তাই S ফাঁকা, আর সব n-এ P(n) সত্য। ∎

উল্টো দিকও প্রমাণ করা যায়: induction থেকে well-ordering আসে। দুটি একে অপরের সমতুল্য; সেই প্রমাণ আর well-ordering-এর সরাসরি ব্যবহার পর্ব ১১ “Strong induction আর well-ordering”-এ আসবে। শুরু 1 থেকেই হতে হবে, এমন কথা নেই: basis P(b) আর k ≥ b-এর জন্য step প্রমাণ করলে সব n ≥ b-এ P(n) সত্য।

২ · প্রমাণের ছাঁচ — basis, hypothesis আর step

প্রতিটি induction প্রমাণ একই কাঠামোয় লেখা যায়। পরীক্ষায় নম্বরও প্রায়ই এই কাঠামো ধরে দেওয়া হয়, তাই অংশগুলো স্পষ্ট নাম দিয়ে লেখার অভ্যাস করুন।

প্রথম পূর্ণ উদাহরণ সেই অর্ডার-id-এর যোগফল। ∑ চিহ্নে লিখলে ∑_i=1ⁿ i = n(n+1)/2. নিচের stepper-এ প্রতিটি লাইনের কারণ দেখুন; ডান পাশে k = 4 বসিয়ে একই ধাপগুলোর সংখ্যাগত রূপও আছে। “পরে” চাপুন:

1P(n): 1+…+n = n(n+1)/22basis: 1 = 1·2/23IH: 1+…+k = k(k+1)/241+…+k+(k+1)5 = k(k+1)/2 + (k+1)6 = (k+1)(k+2)/27∴ ∀n ≥ 1 P(n)  ∎

পরীক্ষার ধরনের একটি হিসাব: বাজারঘরের ৫১ নম্বর থেকে ১০০ নম্বর পর্যন্ত অর্ডারের id-এর যোগফল কত? সরাসরি সূত্র নেই, কিন্তু প্রমাণিত সূত্র দুবার খাটানো যায়: (1 + … + 100) − (1 + … + 50) = 5050 − 1275 = 3775. একইভাবে 1 + … + 250 = 250·251/2 = 31375. প্রমাণিত সূত্রের সুবিধা এটাই: একবার প্রমাণ হলে যেকোনো n-এ নিশ্চিন্তে বসানো যায়, আলাদা করে যাচাই লাগে না।

৩ · যোগফল — আগে আবিষ্কার, তারপর প্রমাণ

Induction একটি সূত্র প্রমাণ করে, কিন্তু সূত্রটি খুঁজে দেয় না। সূত্র আসে ছোট ক্ষেত্র দেখে অনুমান থেকে। কাজের ক্রম তাই: ছোট n-এ হিসাব → প্যাটার্ন অনুমান → অনেক n-এ যন্ত্রে যাচাই → induction-এ প্রমাণ। নিচের ব্লক প্রথম তিন ধাপ করে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

# ধাপ ১: ছোট n-এ বিজোড় সংখ্যার যোগফল দেখে প্যাটার্ন খোঁজা
for n in range(1, 7):
    odd = [2 * i - 1 for i in range(1, n + 1)]
    print(n, odd, "যোগফল =", sum(odd))

# ধাপ ২: অনুমান করা সূত্রগুলো n = 1..50 পর্যন্ত মিলিয়ে দেখা
claims = [
    ("1+2+...+n = n(n+1)/2",
     lambda n: sum(range(1, n + 1)), lambda n: n * (n + 1) // 2),
    ("1+3+...+(2n-1) = n^2",
     lambda n: sum(2 * i - 1 for i in range(1, n + 1)), lambda n: n * n),
    ("1+3+...+(2n-1) = 3n-2",
     lambda n: sum(2 * i - 1 for i in range(1, n + 1)), lambda n: 3 * n - 2),
    ("1+2+4+...+2^n = 2^(n+1)-1",
     lambda n: sum(2 ** i for i in range(n + 1)), lambda n: 2 ** (n + 1) - 1),
    ("1+3+9+...+3^n = (3^(n+1)-1)/2",
     lambda n: sum(3 ** i for i in range(n + 1)), lambda n: (3 ** (n + 1) - 1) // 2),
]
print()
for name, lhs, rhs in claims:
    bad = [n for n in range(1, 51) if lhs(n) != rhs(n)]
    if bad:
        print(f"{name:31} ভুল; প্রথম ব্যতিক্রম n = {bad[0]}")
    else:
        print(f"{name:31} n = 1..50-এ ঠিক")

1 [1] যোগফল = 1
2 [1, 3] যোগফল = 4
3 [1, 3, 5] যোগফল = 9
4 [1, 3, 5, 7] যোগফল = 16
5 [1, 3, 5, 7, 9] যোগফল = 25
6 [1, 3, 5, 7, 9, 11] যোগফল = 36

1+2+...+n = n(n+1)/2            n = 1..50-এ ঠিক
1+3+...+(2n-1) = n^2            n = 1..50-এ ঠিক
1+3+...+(2n-1) = 3n-2           ভুল; প্রথম ব্যতিক্রম n = 3
1+2+4+...+2^n = 2^(n+1)-1       n = 1..50-এ ঠিক
1+3+9+...+3^n = (3^(n+1)-1)/2   n = 1..50-এ ঠিক

প্রমাণ (induction): P(n) দিয়ে উপরের সমতাটি বোঝাই।

1. Basis: n = 1-এ বাঁ পাশ 1, ডান পাশ 1² = 1. P(1) সত্য।
2. Hypothesis: ধরি কোনো ইচ্ছামতো k ≥ 1-এর জন্য 1 + 3 + … + (2k − 1) = k².
3. Step: P(k+1)-এর শেষ পদ 2(k+1) − 1 = 2k + 1. তাই বাঁ পাশ = [1 + … + (2k − 1)] + (2k + 1) — শুধু পদগুলো আলাদা করে লেখা।
4. বন্ধনীর অংশে hypothesis বসিয়ে = k² + 2k + 1.
5. k² + 2k + 1 = (k + 1)² — বর্গের সূত্র। এটিই P(k+1)-এর ডান পাশ।
6. Basis আর step প্রমাণিত, তাই induction-এর নীতিতে সব n ≥ 1-এ P(n) সত্য। ∎

এবার geometric series (গুণোত্তর ধারা), যেখানে প্রতিটি পদ আগেরটির r গুণ। বাজারঘরের একটি রেফারেল স্কিমে প্রথম দিন ১ জন গ্রাহক, প্রতিদিন নতুন গ্রাহক আগের দিনের দ্বিগুণ হলে n + 1 দিনে মোট 1 + 2 + … + 2ⁿ জন: ঠিক এই ধারা।

প্রমাণ (induction, n = 0 থেকে):

1. Basis n = 0: বাঁ পাশ শুধু r⁰ = 1; ডান পাশ (r − 1)/(r − 1) = 1, কারণ r ≠ 1 বলে হর শূন্য নয়।
2. Hypothesis: ধরি কোনো k ≥ 0-এর জন্য 1 + r + … + rᵏ = (rᵏ⁺¹ − 1)/(r − 1).
3. Step: 1 + … + rᵏ + rᵏ⁺¹ = (rᵏ⁺¹ − 1)/(r − 1) + rᵏ⁺¹ — hypothesis বসিয়ে।
4. একই হরে এনে: = [rᵏ⁺¹ − 1 + rᵏ⁺² − rᵏ⁺¹]/(r − 1) = (rᵏ⁺² − 1)/(r − 1). এটিই P(k+1). ∎

r = 2 বসালে 1 + 2 + … + 2ⁿ = 2ⁿ⁺¹ − 1: n বিটের সব 1 দিয়ে তৈরি binary সংখ্যার মান। r = 1 কেন বাদ, ভাবুন: তখন হর শূন্য, আর যোগফল সরাসরি n + 1.

৪ · অসমতা — basis কোথা থেকে শুরু, সেটিই আসল প্রশ্ন

অসমতার প্রমাণে step-এ সমান চিহ্নের বদলে “>” বা “≥”-এর শিকল চলে, আর একটি নতুন প্রশ্ন আসে: দাবিটি কোন n থেকে সত্য? ভুল শুরুর মান বেছে নিলে প্রমাণ ভেঙে যায়।

1. Basis: 2¹ = 2 > 1.
2. Hypothesis: ধরি কোনো k ≥ 1-এ 2ᵏ > k.
3. Step: 2ᵏ⁺¹ = 2 · 2ᵏ > 2k — hypothesis-কে ধনাত্মক 2 দিয়ে গুণ করলে অসমতা টেকে।
4. 2k = k + k ≥ k + 1, কারণ k ≥ 1. তাই 2ᵏ⁺¹ > k + 1. ∎

প্রথমে খসড়া: n = 1, 2, 3-এ n! = 1, 2, 6 আর 2ⁿ = 2, 4, 8; দাবি মিথ্যা। n = 4-এ 24 > 16. তাই basis n = 4, আর step-এ k ≥ 4 ধরা যাবে।

1. Basis n = 4: 4! = 24 > 16 = 2⁴.
2. Hypothesis: ধরি কোনো k ≥ 4-এ k! > 2ᵏ.
3. Step: (k+1)! = (k+1) · k! — factorial-এর সংজ্ঞা।
4. (k+1) · k! > (k+1) · 2ᵏ — hypothesis-কে ধনাত্মক k + 1 দিয়ে গুণ।
5. (k+1) · 2ᵏ ≥ 2 · 2ᵏ = 2ᵏ⁺¹, কারণ k + 1 ≥ 2. মিলিয়ে (k+1)! > 2ᵏ⁺¹. ∎

মজার ব্যাপার: step-টি আসলে k ≥ 1 থেকেই খাটে (ধাপ ৫-এ শুধু k + 1 ≥ 2 লেগেছে)। দাবিটি n = 1, 2, 3-এ মিথ্যা হয়েও প্রমাণ সম্ভব হলো, কারণ ডমিনোর সারি শুরু হলো চতুর্থটি থেকে। শিক্ষা: step খাটলেই হবে না, basis-ও সঠিক জায়গায় চাই। Step সত্য অথচ basis মিথ্যা হলে কী ঘটে, অনুশীলন ৩-এ দেখবেন।

বাজারঘরের ভাষায়: প্রতি মাসে বিক্রি x অংশ বাড়লে (যেমন x = 0.1 মানে ১০%), n মাস পরে চক্রবৃদ্ধি হারে বৃদ্ধি অন্তত সরল হারের বৃদ্ধির সমান। এখানে induction চলে n-এর ওপর, আর x একটি নির্দিষ্ট কিন্তু ইচ্ছামতো বাস্তব সংখ্যা।

1. Basis n = 0: বাঁ পাশ (1 + x)⁰ = 1, ডান পাশ 1 + 0 = 1; 1 ≥ 1 সত্য।
2. Hypothesis: ধরি কোনো k ≥ 0-এ (1 + x)ᵏ ≥ 1 + kx.
3. Step: (1 + x)ᵏ⁺¹ = (1 + x)ᵏ · (1 + x) — ঘাতের নিয়ম।
4. x > −1 বলে 1 + x > 0; ধনাত্মক সংখ্যা দিয়ে গুণ করলে ≥ টেকে, তাই (1 + x)ᵏ⁺¹ ≥ (1 + kx)(1 + x). শর্ত x > −1 ঠিক এখানেই লাগল।
5. (1 + kx)(1 + x) = 1 + (k + 1)x + kx² ≥ 1 + (k + 1)x, কারণ kx² ≥ 0. ∎

শর্তটি কেন দরকার, একটি counterexample দেখায়: x = −3, n = 3 নিলে (1 − 3)³ = −8, অথচ 1 + 3·(−3) = −8; সমান, ভাঙেনি। কিন্তু n = 5-এ (−2)⁵ = −32 আর 1 − 15 = −14, তাই −32 ≥ −14 মিথ্যা। Hypothesis-এর প্রতিটি শর্ত step-এর কোন লাইনে লাগে, তা চিহ্নিত করার অভ্যাস এই কারণেই জরুরি।

৫ · বিভাজ্যতা — P(k+1)-এর ভেতরে P(k)-কে খুঁজে বের করা

a ∣ b (পড়া হয় “a ভাগ করে b”) মানে এমন পূর্ণসংখ্যা c আছে যাতে b = a·c; এটিই divisibility. বিভাজ্যতার induction-এ কৌশল একটাই: P(k+1)-এর রাশিকে “P(k)-এর রাশি + এমন কিছু যা স্পষ্টতই বিভাজ্য” আকারে ভাঙা।

1. Basis n = 0: 0³ − 0 = 0 = 3 · 0, তাই 3 ∣ 0.
2. Hypothesis: ধরি কোনো k ≥ 0-এ k³ − k = 3m, কোনো পূর্ণসংখ্যা m-এর জন্য।
3. Step: (k+1)³ − (k+1) = k³ + 3k² + 3k + 1 − k − 1 — ঘনের বিস্তার।
4. = (k³ − k) + 3(k² + k) — পদ সাজিয়ে P(k)-এর রাশি আলাদা করা।
5. = 3m + 3(k² + k) = 3(m + k² + k) — hypothesis বসিয়ে। m + k² + k পূর্ণসংখ্যা, তাই 3 ∣ (k+1)³ − (k+1). ∎

এই প্রমাণ induction ছাড়াও হয়: n³ − n = (n − 1)n(n + 1), পরপর তিনটি পূর্ণসংখ্যার গুণফল, যাদের একটি 3-এর গুণিতক। একই উপপাদ্যের দুই প্রমাণ জানা ভালো; পর্ব ০৯-এ এমন case-ভিত্তিক যুক্তি দেখেছেন।

1. Basis n = 0: 7⁰ − 2⁰ = 1 − 1 = 0, যা 5 দিয়ে বিভাজ্য।
2. Hypothesis: ধরি কোনো k ≥ 0-এ 7ᵏ − 2ᵏ = 5m.
3. Step: 7ᵏ⁺¹ − 2ᵏ⁺¹ = 7 · 7ᵏ − 2 · 2ᵏ = 7 · 7ᵏ − 7 · 2ᵏ + 7 · 2ᵏ − 2 · 2ᵏ — একই রাশি যোগ-বিয়োগ (মূল কৌশল)।
4. = 7(7ᵏ − 2ᵏ) + 5 · 2ᵏ — উৎপাদক বের করে।
5. = 7 · 5m + 5 · 2ᵏ = 5(7m + 2ᵏ) — hypothesis বসিয়ে। তাই 5 ∣ 7ᵏ⁺¹ − 2ᵏ⁺¹. ∎

ধাপ ৩-এর “7 · 2ᵏ যোগ-বিয়োগ” কোথা থেকে এলো? খসড়ায় প্রশ্ন করুন: 7ᵏ⁺¹ − 2ᵏ⁺¹-এর ভেতরে 7ᵏ − 2ᵏ কীভাবে আনা যায়? 7 দিয়ে গুণ করলে 7ᵏ⁺¹ − 7 · 2ᵏ পাওয়া যায়; বাকি ফারাক 7 · 2ᵏ − 2 · 2ᵏ = 5 · 2ᵏ, যা 5-এর গুণিতক। প্রমাণ এভাবেই আবিষ্কার হয়, পরে গুছিয়ে লেখা হয়। পর্ব ২২ “Modular arithmetic”-এ দেখবেন, 7 ≡ 2 (mod 5) বলে 7ⁿ ≡ 2ⁿ (mod 5): একই ফল এক লাইনে।

৬ · সেটের ওপর induction — power set-এ 2ⁿ টি subset

বাজারঘরের “কম্বো অফার” বানাতে একটি তালিকার পণ্য থেকে যেকোনো সংগ্রহ বেছে নেওয়া যায়, কিছু না নেওয়াও একটি সংগ্রহ। n টি পণ্য থেকে কতগুলো সংগ্রহ? একটি সেট S-এর সব subset-এর সেটকে বলে power set P(S). (P অক্ষরটি এখানে power set; induction-এর P(n)-এর সঙ্গে গুলিয়ে ফেলবেন না।) সেটের বিস্তারিত পর্ব ১৪ “সেট — সংজ্ঞা, subset, power set আর Cartesian product”-এ আসবে।

প্রমাণ (উপাদানের সংখ্যা n-এর ওপর induction):

1. Basis n = 0: S = ∅, যার একমাত্র subset ∅ নিজে। |P(∅)| = 1 = 2⁰.
2. Hypothesis: ধরি k টি উপাদানের প্রতিটি সেটের ঠিক 2ᵏ টি subset আছে।
3. Step: ধরি |S| = k + 1. S থেকে একটি উপাদান a বেছে নিই, আর T = S − {a}; তখন |T| = k.
4. S-এর প্রতিটি subset হয় a ধারণ করে না, নয়তো করে; দুই দল পরস্পর আলাদা।
5. যে subset-এ a নেই, তারা ঠিক T-এর subset; hypothesis অনুযায়ী এরা 2ᵏ টি।
6. যে subset-এ a আছে, তার থেকে a সরালে T-এর একটি subset পাওয়া যায়, আর T-এর প্রতিটি subset-এ a যোগ করলে এমন একটি subset ফেরত আসে। এই এক-এক মিল থেকে এরাও 2ᵏ টি।
7. মোট 2ᵏ + 2ᵏ = 2ᵏ⁺¹. ∎

খেয়াল করুন, hypothesis-এ “k টি উপাদানের প্রতিটি সেট” বলা জরুরি, কারণ step-এ T একটি নির্দিষ্ট সেট নয়, S থেকে তৈরি যেকোনো সেট। এই প্রমাণটি একটি algorithm-ও বলে দেয়: T-এর সব subset বানান, তারপর প্রতিটির একটি a-সহ কপি জুড়ে দিন। নিচের ব্লকের subsets ফাংশন ঠিক তাই করে, সঙ্গে আগের অংশের অসমতা আর বিভাজ্যতাও যাচাই করে:

from math import factorial

# অসমতা: n! > 2^n কোন n থেকে শুরু হয়?
print(" n   n!  2^n  n! > 2^n")
for n in range(1, 7):
    print(f"{n:2} {factorial(n):4} {2**n:4}  {factorial(n) > 2**n}")
print("n = 4..50:", all(factorial(n) > 2**n for n in range(4, 51)))

# বিভাজ্যতা: n = 0..50
print("3 | n^3 - n  :", all((n**3 - n) % 3 == 0 for n in range(51)))
print("5 | 7^n - 2^n:", all((7**n - 2**n) % 5 == 0 for n in range(51)))

# Power set: recursive সংজ্ঞা, প্রমাণের ধাপের হুবহু প্রতিচ্ছবি
def subsets(items):
    if not items:                 # basis: ফাঁকা সেটের subset শুধু {}
        return [[]]
    first, rest = items[0], items[1:]
    without = subsets(rest)       # অনুমান: rest-এর সব subset
    with_first = [[first] + s for s in without]
    return without + with_first   # দ্বিগুণ হলো

print(subsets(["চাল", "ডাল", "তেল"]))
for n in range(7):
    print(n, len(subsets(list(range(n)))), 2**n)

 n   n!  2^n  n! > 2^n
 1    1    2  False
 2    2    4  False
 3    6    8  False
 4   24   16  True
 5  120   32  True
 6  720   64  True
n = 4..50: True
3 | n^3 - n  : True
5 | 7^n - 2^n: True
[[], ['তেল'], ['ডাল'], ['ডাল', 'তেল'], ['চাল'], ['চাল', 'তেল'], ['চাল', 'ডাল'], ['চাল', 'ডাল', 'তেল']]
0 1 1
1 2 2
2 4 4
3 8 8
4 16 16
5 32 32
6 64 64

৭ · L-tromino দিয়ে বোর্ড ঢাকা — প্রমাণ যখন নিজেই algorithm

বাজারঘরের গুদামের মেঝে 8 × 8 বর্গাকার টাইলের ঘরে ভাগ করা। একটি ঘরে একটি পিলার দাঁড়িয়ে, বাকি ৬৩টি ঘর L আকৃতির তাক দিয়ে ঢাকতে হবে, কোনো ফাঁক বা ওভারল্যাপ ছাড়া। প্রতিটি তাক একটি L-tromino: তিনটি বর্গ জুড়ে L আকৃতি, অর্থাৎ ২×২ বর্গ থেকে একটি ঘর বাদ। পিলার যেখানেই থাকুক, এটি কি সবসময় সম্ভব?

আগে একটি সহজ যাচাই: ঘরের সংখ্যা 4ⁿ − 1, আর প্রতিটি tromino ৩টি ঘর নেয়, তাই 3 ∣ 4ⁿ − 1 হতেই হবে। এটিও induction-এ প্রমাণ করা যায় (উপপাদ্য ৫.২-এর কৌশলে), আর 8 × 8-এ (64 − 1)/3 = 21টি tromino লাগবে।

প্রমাণ:

1. Basis n = 1: 2 × 2 বোর্ড থেকে একটি ঘর সরালে বাকি তিন ঘর নিজেই একটি L-tromino.
2. Hypothesis: ধরি কোনো k ≥ 1-এর জন্য 2ᵏ × 2ᵏ মাপের প্রতিটি deficient board, সরানো ঘর যেখানেই থাকুক, ঢাকা যায়।
3. Step: একটি 2ᵏ⁺¹ × 2ᵏ⁺¹ বোর্ড নিই, একটি ঘর সরানো। মাঝখান দিয়ে দুটি রেখা টেনে বোর্ডটিকে চারটি 2ᵏ × 2ᵏ ভাগে কাটি। সরানো ঘরটি ঠিক একটি ভাগে পড়ে।
4. বাকি তিন ভাগের প্রতিটির যে কোণটি বোর্ডের কেন্দ্র ছোঁয়, সেই তিনটি ঘর মিলে একটি L-tromino; সেটি বসাই।
5. এখন চারটি ভাগের প্রতিটি 2ᵏ × 2ᵏ মাপের, আর প্রতিটিতে ঠিক একটি ঘর আগে থেকেই ঢাকা বা সরানো। তাই প্রতিটি একটি deficient board, আর hypothesis অনুযায়ী প্রতিটি ঢাকা যায়।
6. চার ভাগের ঢাকনা আর মাঝের tromino মিলে পুরো বোর্ড ঢাকা। ∎

প্রমাণটি সরাসরি একটি recursive algorithm: “ভাগ করুন, মাঝে L বসান, প্রতিটি ভাগে একই কাজ”। 4 × 4 বোর্ডে, যেখানে সারি ২, কলাম ৩-এর ঘর (X) সরানো, পুরো কাজটি ধাপে ধাপে দেখুন:

1def tile(board, hole):2  if size == 1: return3  split into 4 quarters4  put one L at the centre5  for q in quarters: tile(q)

এবার আসল 8 × 8 গুদাম, পিলার সারি ৬, কলাম ৩-এ (০ থেকে গুনলে (5, 2)). নিচের প্রোগ্রাম প্রমাণের ধাপগুলোই চালায় আর বোর্ড ছাপে; প্রতিটি অক্ষর একটি tromino, “.” পিলার:

from string import ascii_uppercase

def tile(board, top, left, size, hr, hc, names):
    # (top, left) কোণের size×size অংশ; (hr, hc) ঘরটি আগেই ভরা বা ফাঁকা
    if size == 1:
        return                      # basis: ১×১, কিছু বসানোর নেই
    h = size // 2
    piece = next(names)
    quads = [(top, left), (top, left + h), (top + h, left), (top + h, left + h)]
    middle = [(top + h - 1, left + h - 1), (top + h - 1, left + h),
              (top + h, left + h - 1), (top + h, left + h)]
    for (qr, qc), (mr, mc) in zip(quads, middle):
        if qr <= hr < qr + h and qc <= hc < qc + h:
            tile(board, qr, qc, h, hr, hc, names)   # ফাঁকা ঘর এই ভাগে
        else:
            board[mr][mc] = piece                   # মাঝের L-এর একটি ঘর
            tile(board, qr, qc, h, mr, mc, names)

N, hole = 8, (5, 2)
board = [["." for _ in range(N)] for _ in range(N)]
names = iter(ascii_uppercase)
tile(board, 0, 0, N, *hole, names)
for row in board:
    print(" ".join(row))

cells = [x for row in board for x in row if x != "."]
used = sorted(set(cells))
print("tromino:", len(used), "| প্রতিটির ঘর:", {cells.count(c) for c in used})
L = all(len({r for r, c in p}) == 2 and len({c for r, c in p}) == 2
        for p in ([(i, j) for i in range(N) for j in range(N) if board[i][j] == x] for x in used))
print("সব L-আকৃতির?", L)
print("ফাঁকা ঘর:", sum(row.count(".") for row in board), "| (64-1)/3 =", (N * N - 1) // 3)

C C D D H H I I
C B B D H G G I
E B F F J J G K
E E F A A J K K
M M N N A R S S
M L . N R R Q S
O L L P T Q Q U
O O P P T T U U
tromino: 21 | প্রতিটির ঘর: {3}
সব L-আকৃতির? True
ফাঁকা ঘর: 1 | (64-1)/3 = 21

৮ · ভুল induction — “সব ঘোড়ার রং এক” আর অন্য ফাঁদ

Induction-এর কাঠামো এত পরিষ্কার যে ভুল প্রমাণও সহজে বিশ্বাসযোগ্য দেখায়। সবচেয়ে বিখ্যাত উদাহরণ:

সিদ্ধান্তটি নিশ্চিতভাবে মিথ্যা: একটি কালো আর একটি সাদা ঘোড়াই counterexample. তাহলে ভুলটা কোথায়? Basis ঠিক, hypothesis ঠিকভাবে লেখা। সমস্যা step-এর “প্রতিটি k ≥ 1” অংশে। Stepper-এ খুঁজুন:

1P(n): যেকোনো n ঘোড়া এক রং2basis: n = 1 ✓3IH: যেকোনো k ঘোড়া এক রং4A = h1..hk, B = h2..hk+15A এক রং, B এক রং (IH)6মিল ঘোড়া দিয়ে A = B রং

একই পরীক্ষা যন্ত্রে: প্রতিটি k + 1-এর জন্য দুই দল আর তাদের মিল ছাপি।

# "সব ঘোড়ার রং এক" প্রমাণের inductive step যন্ত্রে খোলা
def step(m):                       # m = k + 1টি ঘোড়া
    horses = list(range(1, m + 1))
    a = horses[:-1]                # শেষটি বাদ: k টি
    b = horses[1:]                 # প্রথমটি বাদ: k টি
    common = sorted(set(a) & set(b))
    return a, b, common

for m in range(2, 6):
    a, b, common = step(m)
    verdict = "রং জোড়া লাগে" if common else "কোনো সেতু নেই!"
    print(f"k+1 = {m}: A = {a}, B = {b}, মিল = {common} -> {verdict}")

# দাবিটি নিজেই মিথ্যা: দুটি ঘোড়ার একটি counterexample
colours = {1: "কালো", 2: "সাদা"}
print("২টি ঘোড়া:", colours, "| সব এক রং?", len(set(colours.values())) == 1)

k+1 = 2: A = [1], B = [2], মিল = [] -> কোনো সেতু নেই!
k+1 = 3: A = [1, 2], B = [2, 3], মিল = [2] -> রং জোড়া লাগে
k+1 = 4: A = [1, 2, 3], B = [2, 3, 4], মিল = [2, 3] -> রং জোড়া লাগে
k+1 = 5: A = [1, 2, 3, 4], B = [2, 3, 4, 5], মিল = [2, 3, 4] -> রং জোড়া লাগে
২টি ঘোড়া: {1: 'কালো', 2: 'সাদা'} | সব এক রং? False

আরও তিনটি সাধারণ ভুল

• Basis বাদ দেওয়া: “2 ∣ (n² + n + 1)” দাবির step নিখুঁতভাবে খাটে, অথচ দাবিটি কোনো n-এই সত্য নয় (অনুশীলন ৩)। Step শুধু বলে “একটি পড়লে পরেরটি পড়ে”; প্রথমটিকে কেউ না ফেললে কিছুই পড়ে না।
• P(k+1) দিয়ে শুরু করা: P(k+1)-কে সত্য ধরে সরল করতে করতে একটি সত্য বাক্যে পৌঁছানো (২ নম্বর অংশের সতর্কবার্তা)। প্রতিটি ধাপ উল্টানো যায় এমন হলে সেটিকে উল্টো ক্রমে লিখে প্রমাণ বানানো যায়; নইলে সেটি প্রমাণই নয়। একটি সতর্ক উদাহরণ: “x = 1” থেকে দুই পাশ বর্গ করলে x² = 1, যা সত্য; কিন্তু x² = 1 থেকে x = 1 ফেরত আসে না (x = −1-ও হয়)। অর্থাৎ সত্য উপসংহারে পৌঁছানো শুরুর বাক্যকে সত্য করে না।
• Hypothesis-কে সব k-এ ধরে নেওয়া: “ধরি সব n-এ P(n) সত্য” লিখলে উপসংহারটিই ধরে নেওয়া হলো। লিখতে হবে “একটি ইচ্ছামতো k-এর জন্য P(k)”.

৯ · প্রোগ্রামিংয়ে induction — recursion আর তার সঠিকতা

Recursion মানে একটি ফাংশন নিজেকেই ছোট ইনপুট দিয়ে ডাকে, আর সবচেয়ে ছোট ইনপুটে, অর্থাৎ base case-এ, সরাসরি উত্তর দেয়। Induction আর recursion একই ধারণার দুই রূপ:

ফলে recursive কোড ঠিক কি না, তার স্বাভাবিক প্রমাণ induction. ৬ নম্বর অংশের subsets ফাংশনের দাবি: “n টি উপাদানের তালিকা দিলে এটি প্রতিটি subset ঠিক একবার করে ফেরত দেয়”। প্রমাণ উপপাদ্য ৬.১-এর হুবহু: n = 0-এ [[]], আর ধরে নিলে যে subsets(rest) ঠিক, তখন without হলো first-বিহীন সব subset আর with_first হলো first-সহ সব subset, দুই দলে কোনো মিল নেই। বাজারঘরের অ্যাপে ক্যাটাগরির ভেতরে ক্যাটাগরি (ইলেকট্রনিক্স → মোবাইল → চার্জার) দেখানোর recursive মেনুও একইভাবে প্রমাণ করা যায়, তবে সেখানে induction সংখ্যার ওপর নয়, গাছের গঠনের ওপর চলে; একে বলে structural induction, যা পর্ব ১২ “Recursive সংজ্ঞা আর structural induction”-এ আসবে।

Python-এ recursion কীভাবে লেখা হয় আর call stack-এ কী ঘটে, তা Python প্রোগ্রামিং কোর্সের পর্ব ১৩-এ আছে; algorithm হিসেবে recursion DSA কোর্সের পর্ব ০৭-এ। Recursive algorithm আর loop-এর সঠিকতা induction ও loop invariant দিয়ে প্রমাণের algorithm-দিক DSA কোর্সের পর্ব ০৩-এ; তার পেছনের যুক্তিবিদ্যা (Hoare logic) পর্ব ১৩ “Program-এর সঠিকতা”-তে আসবে। কিছু recursion-এ k + 1-এর উত্তরের জন্য শুধু k নয়, আগের অনেক মান লাগে (যেমন Fibonacci); তখন দরকার strong induction, পর্ব ১১-এর বিষয়।

১০ · AI-এর যুগে — AI-এর induction প্রমাণ কীভাবে যাচাই করবেন

AI সহকারী induction প্রমাণ খুব গুছিয়ে লেখে, কারণ ছাঁচটি সবার জানা। ঠিক এই কারণেই ভুলগুলো চোখ এড়িয়ে যায়: শিরোনাম ঠিক, বীজগণিত ভুল। যে ভুলগুলো বেশি দেখা যায়:

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

• দাবিটি Python-এ ছোট n-এর জন্য মিলিয়েছি; কোনো counterexample নেই
• Basis-এর মান দাবির শুরুর মানের সঙ্গে মেলে, আর দুই পাশ নিজে হিসাব করেছি
• Hypothesis শুধু একটি ইচ্ছামতো k-এর জন্য, আর step-এ সেটি সত্যিই ব্যবহার হয়েছে
• Step এক পাশ থেকে অন্য পাশে গেছে, P(k+1) ধরে নিয়ে শুরু করেনি
• প্রতিটি সমতায় k = 3 বসিয়ে সংখ্যায় মিলিয়েছি
• সবচেয়ে ছোট k-তে step-এর প্রতিটি যুক্তি খাটে কি না দেখেছি (ঘোড়ার ফাঁদ)
• উল্লেখ করা উপপাদ্য বা বইয়ের নাম বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি