Induction
আরোহ পদ্ধতি
অসীম সংখ্যক ক্ষেত্র সসীম যুক্তিতে প্রমাণ করার একমাত্র হাতিয়ার — base case আর inductive step। Recursion-এর গাণিতিক যমজ।
also: mathematical induction, structural induction
দুইটা ধাপ প্রমাণ করলেই অসীম সংখ্যক দাবি প্রমাণিত:
Base case: P(n₀) সত্য
Inductive step: ∀k ≥ n₀ : P(k) → P(k+1)তিনটা রূপ:
| রূপ | Inductive hypothesis |
|---|---|
| Weak | P(k) সত্য |
| Strong | P(n₀) … P(k) — সবগুলো সত্য |
| Structural | উপাদান-structure-গুলোর জন্য সত্য |
Strong লাগে যখন P(k+1) প্রমাণ করতে আরো আগের কিছু দরকার —
যেমন Fibonacci (দুইটা আগের মান) বা prime factorisation।
Recursion-এর সাথে সম্পর্ক — এটাই মূল অন্তর্দৃষ্টি:
| Induction | [[recursion]] |
|---|---|
P(n) | function-এর specification |
| Base case | if n == 0: return … |
| Inductive hypothesis | recursive call ঠিক কাজ করে — এই বিশ্বাস |
| Inductive step | সেই ফল দিয়ে উত্তর বানানো |
| [[well-ordering-principle]] | argument ছোট হচ্ছে, base-এ পৌঁছাবে |
“Recursive leap of faith”-টা আসলে inductive hypothesis। Recursion লিখতে শেখা মানে induction-এ চিন্তা করতে শেখা।
নাম নিয়ে সতর্কতা: mathematical induction deductive ও নিশ্চিত। “কয়েকটা উদাহরণ দেখে সাধারণীকরণ” (inductive reasoning) সম্পূর্ণ ভিন্ন জিনিস এবং প্রমাণ নয়।