Mathematical Induction — অসীমকে সসীম যুক্তিতে ধরা

P(n): “|S| = n হলে |𝒫(S)| = 2ⁿ”, যেখানে 𝒫(S) = power set।

Base case (n = 0): খালি সেট ∅-এর একমাত্র উপসেট ∅ নিজে। তাই |𝒫(∅)| = 1 = 2⁰ ✓

Inductive step: ধরি P(k) সত্য — k উপাদানের যেকোনো সেটের 2ᵏ টা উপসেট আছে।

এবার |S| = k + 1 নিন। একটা উপাদান x ∈ S বেছে নিন, আর ধরি S' = S \ {x}, তাই |S'| = k।

S-এর প্রতিটা উপসেট T -কে দুই দলে ভাগ করা যায়:

• যেগুলোতে x নেই: এরা ঠিক S'-এর উপসেট। সংখ্যা = |𝒫(S')| = 2ᵏ (IH)
• যেগুলোতে x আছে: প্রতিটা এমন T-কে T = T' ∪ {x} আকারে লেখা যায় যেখানে T' ⊆ S'। এই সঙ্গতিটা একের সাথে এক, তাই সংখ্যাও 2ᵏ

দুইটা দল পরস্পর বিচ্ছিন্ন এবং একসাথে সব উপসেট ঢাকে (প্রতিটা উপসেটে হয় x আছে নয় নেই — exhaustive)।

$|\mathcal{P}(S)| = 2^k + 2^k = 2 \cdot 2^k = 2^{k+1} \quad\blacksquare$

একটা সুন্দর বিকল্প দৃষ্টি: প্রতিটা উপসেটকে একটা n-bit string হিসেবে ভাবুন — bit i বলে i-তম উপাদানটা আছে কি নেই। n bit-এর সম্ভাব্য string 2ⁿ টা, আর প্রতিটা string ঠিক একটা উপসেট বোঝায়।

এই bit-string দৃষ্টিটাই বাস্তবে ব্যবহার হয় — bitmask দিয়ে subset enumeration:

def subsets(items):
    n = len(items)
    for mask in range(1 \<\< n):
        yield [items[i] for i in range(n) if mask & (1 \<\< i)]

Level 1-এ bit manipulation, Level 6-এ subset enumeration আর bitmask DP — দুটোই এই ধারণার উপর দাঁড়ানো।

Strong induction লাগবে।

কারণ fib(n) -এর correctness প্রমাণ করতে আপনার fib(n-1) এবং fib(n-2) — দুটোরই correctness লাগে। Weak IH শুধু P(n-1) দেয়, P(n-2) দেয় না।

প্রমাণ. P(n): “fib(n) = Fₙ”, যেখানে F₀ = 0, F₁ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂।

Base cases (দুইটা লাগবে):

• fib(0) = 0 = F₀ ✓
• fib(1) = 1 = F₁ ✓

Inductive step: n ≥ 2 নিন। ধরি 0 ≤ j \< n-এর সব j-এর জন্য fib(j) = Fⱼ (strong IH)।

যেহেতু n-1 \< n এবং n-2 \< n, IH দুটোতেই প্রযোজ্য:

fib(n) = fib(n-1) + fib(n-2) = Fₙ₋₁ + Fₙ₋₂ = Fₙ  ✓ ∎

দুইটা base case কেন জরুরি: যদি শুধু n = 0 base case রাখতেন, তাহলে n = 1-এর জন্য inductive step-এ fib(-1) লাগত — যা সংজ্ঞায়িত নয়।

কোডেও একই: if n == 0: return 0 লিখে n == 1-এর case ভুলে গেলে fib(1) → fib(0) + fib(-1) → অসীম recursion (negative-এ নেমে যাবে)।

পার্শ্ব-পর্যবেক্ষণ: এই naive version-এর complexity O(φⁿ) যেখানে φ ≈ 1.618। fib(50) চালাতে মিনিট লাগে। Memoization দিয়ে O(n), matrix exponentiation দিয়ে O(log n) — Level 6-এ দেখব।

def hanoi(n, src, dst, aux, moves):
    if n == 0: return
    hanoi(n-1, src, aux, dst, moves)     # উপরের n-1 টা সরাও
    moves.append((src, dst))              # সবচেয়ে বড়টা সরাও
    hanoi(n-1, aux, dst, src, moves)      # n-1 টা ফিরিয়ে আনো

অংশ ১ — algorithm ঠিক 2ⁿ − 1 চাল দেয়।

M(n) = n চাকতির জন্য চাল সংখ্যা। Recurrence:

$M(0) = 0, \qquad M(n) = 2M(n-1) + 1$

P(n): M(n) = 2ⁿ − 1

Base: M(0) = 0 = 2⁰ − 1 = 0 ✓

Step: ধরি M(k) = 2ᵏ − 1।

$M(k+1) = 2M(k) + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 2 + 1 = 2^{k+1} - 1 \quad\blacksquare$

অংশ ২ — এর চেয়ে কম চালে সম্ভব নয়।

L(n) = সর্বনিম্ন প্রয়োজনীয় চাল। দেখাব L(n) ≥ 2ⁿ − 1।

Base: L(0) = 0 ≥ 0 ✓

Step: ধরি L(k) ≥ 2ᵏ − 1।

যেকোনো বৈধ সমাধানে, সবচেয়ে বড় চাকতিটাকে অন্তত একবার সরাতেই হবে। কিন্তু সেটা সরানোর মুহূর্তে:

• তার উপরে কোনো চাকতি থাকতে পারে না
• গন্তব্য খুঁটিও খালি থাকতে হবে

অর্থাৎ বাকি k টা চাকতি সবগুলো তৃতীয় খুঁটিতে থাকতে হবে — একটা সম্পূর্ণ বৈধ স্তূপ হিসেবে। সেখানে পৌঁছাতে অন্তত L(k) চাল।

তারপর বড় চাকতিটা সরানো: ১ চাল।

তারপর সেই k টা চাকতিকে গন্তব্যে আনা: আবার অন্তত L(k) চাল।

$L(k+1) \ge 2L(k) + 1 \ge 2(2^k - 1) + 1 = 2^{k+1} - 1 \quad\blacksquare$

দুই অংশ মিলিয়ে: algorithm 2ⁿ − 1 দেয়, আর 2ⁿ − 1-এর কম সম্ভব নয়। অতএব algorithm-টা optimal।

তাৎপর্য: এটা একটা lower bound proof — algorithm design-এর সবচেয়ে গুরুত্বপূর্ণ ধরনের প্রমাণ। এটা বলে “আরো ভালো algorithm খুঁজে লাভ নেই”।

কিংবদন্তির ৬৪ চাকতির Hanoi tower: 2⁶⁴ − 1 ≈ 1.8 × 10¹⁹ চাল। সেকেন্ডে একটা চাল দিলে প্রায় ৫৮৫ বিলিয়ন বছর — মহাবিশ্বের বয়সের ৪২ গুণ।

Level 6-এ আমরা comparison sort-এর Ω(n log n) lower bound দেখব, যেটা একই ধরনের যুক্তি।

একাধিক ভুল আছে।

১. দাবিটাই অস্পষ্ট। “n টা মুদ্রা দিয়ে যেকোনো পরিমাণ ≥ n” — এটা কী বলছে পরিষ্কার নয়। মুদ্রা সংখ্যা ঠিক n হতে হবে? নাকি সর্বোচ্চ n?

২. Base case ভুল। n = 1-এ দাবি হলো “১টা মুদ্রায় যেকোনো পরিমাণ ≥ 1 বানানো যায়”। কিন্তু ১টা মুদ্রায় শুধু ৩ বা ৫ টাকা হয় — ১, ২, ৪ টাকা হয় না। Base case মিথ্যা।

৩. Inductive step অর্থহীন। “আরেকটা মুদ্রা যোগ করলে k+1 টাকা হবে” — কোন মুদ্রা? ৩ যোগ করলে k+3, ৫ যোগ করলে k+5। k+1 পাওয়ার কোনো উপায় বলা হয়নি। IH ব্যবহারই হয়নি ঠিকভাবে।

সঠিক দাবি ও প্রমাণ:

দাবি: n ≥ 8-এর প্রতিটা পূর্ণসংখ্যা টাকা ৩ আর ৫ টাকার মুদ্রা দিয়ে বানানো যায়।

Base cases (তিনটা লাগবে):

• 8 = 3 + 5 ✓
• 9 = 3 + 3 + 3 ✓
• 10 = 5 + 5 ✓

Inductive step: ধরি 8 ≤ j ≤ k-এর সব j বানানো যায় (strong IH), আর k ≥ 10 নিন।

k + 1 ≥ 11, তাই (k+1) − 3 = k − 2 ≥ 8। Strong IH অনুযায়ী k−2 বানানো যায়। তার সাথে একটা ৩ টাকার মুদ্রা যোগ করলে k+1 ✓ ∎

কেন n = 8 থেকে: 1, 2, 4, 7 — এই চারটা বানানো যায় না। (7: 3+3=6, 3+5=8 — মাঝে কিছু নেই।)

কেন তিনটা base case: inductive step k−2-এ ফিরে যায়, তাই পরপর তিনটা মান জানা থাকতে হবে যাতে শৃঙ্খল ভাঙে না।

এটা Chicken McNugget theorem (বা Frobenius coin problem) নামে পরিচিত: a আর b সহমৌলিক হলে বানানো যায় না এমন সর্বোচ্চ সংখ্যা ab − a − b। এখানে 3·5 − 3 − 5 = 7 ✓

P(T): “leaves(T) ≤ 2^height(T)”

Base case (T = Leaf): leaves = 1, height = 0。 1 ≤ 2⁰ = 1 ✓

Inductive step (T = Node(L, R)): ধরি P(L) আর P(R) সত্য (structural IH):

leaves(L) ≤ 2^height(L)
leaves(R) ≤ 2^height(R)

ধরি h = height(T) = 1 + max(height(L), height(R))। তাহলে height(L) ≤ h − 1 এবং height(R) ≤ h − 1।

তাৎপর্য — এটাই balanced tree-র ভিত্তি।

অসমতাটা উল্টে লিখুন:

$\text{height}(T) \ge \log_2(\text{leaves}(T))$

অর্থাৎ n টা leaf রাখতে হলে height অন্তত log₂ n হতেই হবে।

এই সীমাটা বলে দেয়:

• কোনো binary tree log₂ n -এর চেয়ে কম height-এ n টা leaf রাখতে পারে না — তাই balanced BST-র O(log n) search-ই সর্বোত্তম সম্ভব
• Comparison sort-এর decision tree-তে n! টা সম্ভাব্য ফলাফল (leaf), তাই height ≥ log₂(n!) = Θ(n log n)। এটাই comparison sort-এর বিখ্যাত lower bound
• B-tree-তে branching factor b হলে height ≥ log_b n — এই কারণেই database index-এ b বড় রাখা হয় (page-এর সমান), যাতে disk seek কম লাগে

Level 6-এ এই তিনটাই বিস্তারিত আসবে, আর Level 8-এ B-tree-র page আকার নির্বাচনের হিসাবটা এই অসমতা থেকেই আসবে।