গাণিতিক ইনডাকশন

১ · ইনডাকশনের মূলনীতি

গাণিতিক ইনডাকশন (Mathematical Induction)Mathematical Inductionএমন একটি প্রমাণ পদ্ধতি যা "সব n≥base-এর জন্য P(n) সত্য" প্রমাণ করে দুইটি ধাপে — একটি ভিত্তি (base case) ও একটি ধাপ-থেকে-ধাপে সংযোগ (inductive step)। একটি ডমিনো চেইনের মতো কাজ করে — যদি প্রথম ডমিনোটি পড়ে (base case), এবং প্রতিটি ডমিনো পড়লে তার পরেরটিও পড়বে এটি নিশ্চিত থাকে (inductive step), তাহলে গোটা চেইনটাই একে একে পড়বে।

ইনডাকশন দিয়ে "সব $n \ge$ base-এর জন্য P(n) সত্য" প্রমাণ করতে দুটি ধাপ লাগে —

1. Base case: P(base) সত্য তা সরাসরি দেখানো (সাধারণত base=0 বা 1)।
2. Inductive step: P(k) সত্য ধরে নিয়ে (এটিকে Inductive HypothesisInductive Hypothesis (IH)ইনডাকশনের inductive step-এ P(k) সত্য এই ধরে নেওয়া অনুমান — এটি প্রমাণ করা হয় না, শুধু ব্যবহার করা হয় P(k+1) প্রমাণ করতে। বা IH বলা হয়), তা থেকে P(k+1) প্রমাণ করা।

২ · Worked Example ১ — যোগফলের সূত্র

দাবি: সব $n \ge 1$-এর জন্য, $1+2+\cdots+n = \dfrac{n(n+1)}{2}$।

Base case (n=1): বামপক্ষ $=1$। ডানপক্ষ $=\dfrac{1(2)}{2}=1$। উভয়ে মিলে যায় — $1=1$। ✓

Inductive step: ধরি (IH) $1+2+\cdots+k = \dfrac{k(k+1)}{2}$ সত্য কোনো একটি $k \ge 1$-এর জন্য। আমাদের দেখাতে হবে $1+2+\cdots+k+(k+1) = \dfrac{(k+1)(k+2)}{2}$।

$1+2+\cdots+k+(k+1) = \underbrace{\dfrac{k(k+1)}{2}}_{\text{IH দিয়ে}} + (k+1) = (k+1)\left[\dfrac{k}{2}+1\right] = \dfrac{(k+1)(k+2)}{2}$

এটি ঠিক formula-টি $n=k+1$ বসিয়ে যা পাওয়া যেত তার সাথে মেলে। ✓ ইনডাকশনের মূলনীতি অনুযায়ী, দাবিটি সব $n \ge 1$-এর জন্য সত্য। $\blacksquare$

৩ · Worked Example ২ — $2^n > n$

দাবি: সব $n \ge 1$-এর জন্য, $2^n > n$।

Base case (n=1): $2^1 = 2 > 1$। ✓

Inductive step: ধরি (IH) $2^k > k$ সত্য কোনো $k \ge 1$-এর জন্য। দেখাতে হবে $2^{k+1} > k+1$।

$2^{k+1} = 2 \cdot 2^k \overset{\text{IH}}{>} 2k \ge k+1 \quad (\text{যেহেতু } k \ge 1 \Rightarrow 2k \ge k+1)$

তাই $2^{k+1} > k+1$। ✓ ইনডাকশনের মূলনীতি অনুযায়ী, দাবিটি সব $n \ge 1$-এর জন্য সত্য। $\blacksquare$

৪ · Strong Induction

Strong InductionStrong Inductionইনডাকশনের একটি রূপ যেখানে inductive step-এ শুধু P(k) নয়, বরং base থেকে k পর্যন্ত সব P(base),...,P(k) সত্য ধরে নেওয়া যায়। -এ inductive step আরও শক্তিশালী — শুধু P(k) নয়, P(base) থেকে P(k) পর্যন্ত সবগুলো সত্য ধরে নিয়ে P(k+1) প্রমাণ করা হয়।

এটি দরকার হয় যখন P(k+1) সরাসরি P(k)-এর উপর নির্ভর না করে, বরং কোনো ছোট মানের উপর নির্ভর করে যা k-এর চেয়ে অনেক ছোট হতে পারে। ক্লাসিক উদাহরণ: "প্রতিটি পূর্ণসংখ্যা $>1$-এর একটি প্রাইম ফ্যাক্টরাইজেশন আছে" — যদি n যৌগিক (composite) হয়, তাহলে $n=ab$ যেখানে $a,b$ উভয়ে $n$-এর চেয়ে ছোট কিন্তু নির্দিষ্টভাবে $n-1$ নাও হতে পারে — তাই শুধু "P(n-1) সত্য ধরে নেওয়া" যথেষ্ট নয়, "P(1) থেকে P(n-1) পর্যন্ত সব সত্য ধরে নেওয়া" দরকার।

for n in range(1, 20):
    lhs = sum(range(1, n + 1))
    rhs = n * (n + 1) // 2
    assert lhs == rhs, f"n={n}-এ মিল নেই"

print("যাচাই সম্পন্ন — n=1 থেকে 19 পর্যন্ত সব মিলেছে")