0.4 — প্রমাণের কৌশল (Proof Techniques)¶

এই অধ্যায়ে কী শিখব: proof (প্রমাণ) কী; direct proof (সরাসরি প্রমাণ); proof by contrapositive (বিপরীত-প্রতিজ্ঞা দিয়ে প্রমাণ); proof by contradiction (অসঙ্গতি-প্রমাণ) এবং \(\sqrt{2}\) অমূলদ প্রমাণ; mathematical induction (গাণিতিক আরোহ) ও strong induction; আর disproof by counterexample (প্রতিউদাহরণ দিয়ে খণ্ডন)।

উৎস (source): নতুন (foundation) · proof: Euclid; induction: Pascal, Peano।

১. কেন শিখব? (Motivation)¶

গণিতে কোনো দাবি করলেই হয় না — প্রমাণ (proof) করতে হয়। প্রমাণ মানে একটা নিরেট যুক্তির শিকল: প্রতিটা পদক্ষেপ আগেরটা থেকে অনিবার্যভাবে বেরিয়ে আসে, কোনো ফাঁক নেই।

কিন্তু প্রমাণ করার কৌশল কি একটাই? মোটেই না। একটা বাড়িতে ঢোকার মতো — সামনের দরজা, পেছনের দরজা, জানালা — সব পথেই ভেতরে পৌঁছানো যায়; কোন পথটা সহজ সেটা নির্ভর করে সমস্যার চরিত্রের উপর।

এই অধ্যায়ে পাঁচটা প্রধান কৌশল শিখব:

কৌশল	কখন কাজে লাগে
Direct proof	স্বাভাবিক সরলরৈখিক পথ যখন পাওয়া যায়
Contrapositive	"হলে" সরাসরি ধরা কঠিন, উল্টো ধরলে সহজ
Contradiction	ধরে নিই দাবিটা মিথ্যা, দেখি কোথায় গোলমাল বাধে
Induction	প্রাকৃতিক সংখ্যার জন্য ডমিনোর মতো শিকল
Counterexample	একটা "সব"-দাবিকে মাত্র একটা উদাহরণ দিয়ে ভেঙে দাও

0.1-এ তুমি দেখেছিলে \(p \to q \equiv \neg q \to \neg p\) — এটাই contrapositive-এর ভিত্তি। এখন সেটা হাতে-কলমে ব্যবহার করব।

মূল কথা

Proof শেখা মানে কৌশলের একটা টুলকিট গড়া। যত বেশি কৌশল জানবে, তত বেশি সমস্যার দরজা খুলবে।

২. মূল ধারণা (Core idea)¶

Proof (প্রমাণ) কী?¶

একটা theorem (উপপাদ্য) হলো এমন একটা দাবি যেটা সত্য বলে আমরা জানি কারণ সেটা প্রমাণিত। Proof হলো সেই প্রমাণের দলিল — সংজ্ঞা, axiom (স্বতঃসিদ্ধ) ও আগে-প্রমাণিত theorem থেকে শুরু করে পদে পদে logic ব্যবহার করে বক্তব্যে পৌঁছানোর রাস্তা।

বেশিরভাগ theorem-এর রূপ হয়: "\(P\) হলে \(Q\)" — যেমন "যদি \(n\) জোড় হয়, তবে \(n^2\) জোড়।" এখানে \(P\) হলো hypothesis (প্রাক-শর্ত) আর \(Q\) হলো conclusion (সিদ্ধান্ত)।

Proof-এর কৌশলগুলোর স্বজ্ঞা¶

সরাসরি (Direct): \(P\) সত্য ধরো, তারপর সোজা পথে \(Q\)-তে পৌঁছাও।

Contrapositive: 0.1-এর শিক্ষা — \(p \to q\) আর \(\neg q \to \neg p\) একই কথা। তাই "\(Q\) মিথ্যা ধরো, দেখাও \(P\) মিথ্যা হতে বাধ্য।"

Contradiction (অসঙ্গতি): ধরো \(P\) সত্য কিন্তু \(Q\) মিথ্যা (মানে দাবিটা মিথ্যা)। তারপর দেখাও এই ধারণা থেকে এমন কিছু বেরিয়ে আসে যা অসম্ভব — তাহলে মূল ধারণাই ভুল ছিল।

Induction (আরোহ): ডমিনোর মতো। প্রথম ডমিনো পড়লে (base case সত্য) এবং যেকোনো ডমিনো পড়লে পরেরটাও পড়বে (inductive step সত্য) — তাহলে সব ডমিনো পড়বে।

Counterexample (প্রতিউদাহরণ): "সবার জন্য \(Q\) সত্য" খণ্ডন করতে একটামাত্র \(Q\) মিথ্যা এমন উদাহরণ যথেষ্ট।

Induction — ডমিনো চিত্র¶

Induction domino chain চিত্র ১: গাণিতিক আরোহ (mathematical induction) — ডমিনোর শিকল। প্রথমটা ফেললে (base case) এবং প্রতিটা পড়লে পরেরটাও পড়লে (inductive step), সবগুলোই পড়বে।

Induction — Sum-এর দৃশ্যমান প্রমাণ¶

Staircase visual proof of 1+2+...+n চিত্র ২: \(1+2+\cdots+n = \tfrac{n(n+1)}{2}\) — দুটো সিঁড়িকে পাশাপাশি রাখলে একটা \(n \times (n+1)\) আয়তক্ষেত্র পাওয়া যায়। নীল = মূল সিঁড়ি (\(1+2+\cdots+n\)); লাল = উল্টো কপি। মোট \(n(n+1)\), অর্থাৎ প্রতিটা \(\tfrac{n(n+1)}{2}\)।

৩. সংজ্ঞা ও উপপাদ্য (Definitions & Theorems)¶

৩.১ — Direct Proof (সরাসরি প্রমাণ)¶

কৌশল: Direct Proof

লক্ষ্য: \(P \Rightarrow Q\) প্রমাণ করা।

পদ্ধতি: \(P\) সত্য ধরো। সংজ্ঞা ও পূর্বের theorem ব্যবহার করে ধাপে ধাপে দেখাও \(Q\) সত্য।

উদাহরণ — উপপাদ্য ১: যদি \(n\) একটা জোড় (even) পূর্ণসংখ্যা হয়, তবে \(n^2\) ও জোড়।

প্রমাণ:

\(n\) জোড় মানে সংজ্ঞা অনুযায়ী \(n = 2k\) কোনো পূর্ণসংখ্যা \(k\)-এর জন্য।

তাহলে:

\[n^2 = (2k)^2 = 4k^2 = 2(2k^2)\]

\(2k^2\) একটা পূর্ণসংখ্যা (যেহেতু \(k\) পূর্ণসংখ্যা)। তাই \(n^2 = 2 \cdot (\text{পূর্ণসংখ্যা})\), অর্থাৎ \(n^2\) জোড়। \(\blacksquare\)

৩.২ — Proof by Contrapositive (বিপরীত-প্রতিজ্ঞা দিয়ে প্রমাণ)¶

0.1-এ প্রমাণ হয়েছিল:

\[p \to q \;\equiv\; \neg q \to \neg p\]

এটাই contrapositive ব্যবহারের ভিত্তি।

কৌশল: Contrapositive

লক্ষ্য: \(P \Rightarrow Q\) প্রমাণ করা।

পদ্ধতি: বদলে \(\neg Q \Rightarrow \neg P\) প্রমাণ করো — এটা logical equivalence অনুযায়ী একই কথা।

উদাহরণ — উপপাদ্য ২: যদি \(n^2\) বিজোড় (odd), তবে \(n\) বিজোড়।

Direct proof কেন কঠিন: "\(n^2\) বিজোড়" থেকে সরাসরি \(n\)-এর সম্পর্কে কিছু বলা ঝামেলার।

Contrapositive ধরি: "\(n\) বিজোড় নয় (অর্থাৎ \(n\) জোড়) \(\Rightarrow\) \(n^2\) বিজোড় নয় (অর্থাৎ \(n^2\) জোড়)।"

প্রমাণ:

ধরো \(n\) জোড়, তাহলে \(n = 2k\) কোনো পূর্ণসংখ্যা \(k\)-এর জন্য।

\[n^2 = 4k^2 = 2(2k^2)\]

এটা জোড়। তাই contrapositive সত্য, অর্থাৎ মূল theorem-ও সত্য। \(\blacksquare\)

৩.৩ — Proof by Contradiction (অসঙ্গতি-প্রমাণ)¶

কৌশল: Contradiction

লক্ষ্য: \(Q\) সত্য প্রমাণ করা (বা \(P \Rightarrow Q\))।

পদ্ধতি:

ধরো \(Q\) মিথ্যা (অর্থাৎ \(\neg Q\) সত্য)।
এই ধারণা থেকে যুক্তি চালাও।
এমন কিছুতে এসে পৌঁছাও যা clearly মিথ্যা বা স্ব-বিরোধী (contradiction)।
সিদ্ধান্ত: শুরুর ধারণাই ভুল ছিল, তাই \(Q\) সত্য।

উপপাদ্য ৩ (ক্লাসিক): \(\sqrt{2}\) অমূলদ (irrational)¶

এটা গণিতের সবচেয়ে বিখ্যাত proof — প্রাচীন গ্রিক গণিতবিদরা এটা আবিষ্কার করে বিস্মিত হয়েছিলেন।

সংজ্ঞা:

Rational number (মূলদ সংখ্যা): এমন সংখ্যা যাকে \(\frac{p}{q}\) রূপে লেখা যায় যেখানে \(p, q\) পূর্ণসংখ্যা এবং \(q \neq 0\)।
Irrational number (অমূলদ সংখ্যা): যা মূলদ নয়, অর্থাৎ কোনো \(\frac{p}{q}\) রূপে লেখা যায় না।

প্রমাণ (contradiction দিয়ে):

পদক্ষেপ ১: ধরো \(\sqrt{2}\) মূলদ — অর্থাৎ contradiction-এর জন্য ধরো \(\sqrt{2} = \frac{p}{q}\) যেখানে \(p, q\) পূর্ণসংখ্যা, \(q \neq 0\), এবং ভগ্নাংশটা সরলীকৃত (লঘিষ্ঠ আকারে) — মানে \(p\) ও \(q\)-এর কোনো সাধারণ গুণনীয়ক নেই, বিশেষত উভয়েই একসাথে জোড় নয়।

পদক্ষেপ ২: দুদিক বর্গ করো:

\[2 = \frac{p^2}{q^2} \implies p^2 = 2q^2\]

পদক্ষেপ ৩: \(p^2 = 2q^2\) মানে \(p^2\) জোড়। আর 3.1-এর contrapositive থেকে (উপপাদ্য ২): যদি \(p^2\) জোড় তবে \(p\) জোড়।

তাই \(p = 2m\) কোনো পূর্ণসংখ্যা \(m\)-এর জন্য।

পদক্ষেপ ৪: \(p = 2m\) বসাই:

\[(2m)^2 = 2q^2 \implies 4m^2 = 2q^2 \implies q^2 = 2m^2\]

তাহলে \(q^2\) জোড়, তাই (আবার উপপাদ্য ২ দিয়ে) \(q\)-ও জোড়।

পদক্ষেপ ৫ — Contradiction! আমরা পেলাম \(p\) জোড় এবং \(q\) জোড়। কিন্তু শুরুতেই ধরেছিলাম ভগ্নাংশটা সরলীকৃত, অর্থাৎ \(p\) ও \(q\) একসাথে জোড় হতে পারে না। এটাই contradiction (অসঙ্গতি)।

উপসংহার: শুরুর ধারণা — "\(\sqrt{2}\) মূলদ" — ভুল ছিল। তাই \(\sqrt{2}\) অমূলদ। \(\blacksquare\)

সূক্ষ্ম পয়েন্ট

"সরলীকৃত ভগ্নাংশ" ধরাটা গুরুত্বপূর্ণ — এটা না ধরলে \(p\) ও \(q\) উভয়ই জোড় হওয়া contradiction হতো না। যেকোনো মূলদ সংখ্যাকে সরলীকৃত রূপে লেখা যায় — এটা integer-এর একটা basic property।

৩.৪ — Mathematical Induction (গাণিতিক আরোহ)¶

Induction ব্যবহার হয় যখন আমরা প্রমাণ করতে চাই: "সব natural number \(n \geq n_0\)-এর জন্য \(P(n)\) সত্য।"

কৌশল: Mathematical Induction

পদক্ষেপ ১ — Base case (ভিত্তি ক্ষেত্র): দেখাও \(P(n_0)\) সত্য (সাধারণত \(n_0 = 1\))।

পদক্ষেপ ২ — Inductive step (আরোহ পদক্ষেপ): ধরো \(P(k)\) সত্য (এটাই inductive hypothesis (আরোহ-অনুমান)) যেকোনো \(k \geq n_0\)-এর জন্য। এই অনুমান ব্যবহার করে দেখাও \(P(k+1)\)-ও সত্য।

উপসংহার: \(P(n)\) সব \(n \geq n_0\)-এর জন্য সত্য।

উপপাদ্য ৪ (Worked sum): \(\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}\)¶

অর্থাৎ \(1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}\)।

প্রমাণ (induction দিয়ে):

Base case (\(n = 1\)):

\[\text{বাঁয়ে: } \sum_{k=1}^{1} k = 1 \qquad \text{ডানে: } \frac{1 \cdot 2}{2} = 1 \checkmark\]

Inductive step: ধরো \(n = m\)-এর জন্য সত্য, অর্থাৎ inductive hypothesis:

\[1 + 2 + \cdots + m = \frac{m(m+1)}{2}\]

এখন \(n = m+1\)-এর জন্য দেখাতে হবে:

\[1 + 2 + \cdots + m + (m+1) = \frac{(m+1)(m+2)}{2}\]

বাঁয়ের রাশি ভাঙি:

\[\underbrace{1 + 2 + \cdots + m}_{\text{inductive hypothesis দিয়ে } = \frac{m(m+1)}{2}} + (m+1)\]

\[= \frac{m(m+1)}{2} + (m+1) = (m+1)\left(\frac{m}{2} + 1\right) = (m+1) \cdot \frac{m+2}{2} = \frac{(m+1)(m+2)}{2}\]

এটাই ডানের রাশি। তাই \(n = m+1\)-এর জন্যও সূত্র সত্য। \(\blacksquare\)

ছোট চেক (\(n=4\)): \(1+2+3+4 = 10\) এবং \(\frac{4\cdot 5}{2} = 10\) ✓

৩.৫ — Strong Induction (শক্তিশালী আরোহ)¶

সাধারণ induction-এ শুধু \(P(k)\) ধরে \(P(k+1)\) প্রমাণ করা হয়। কিন্তু কখনো \(P(k+1)\) প্রমাণ করতে \(P(1), P(2), \ldots, P(k)\) সবগুলো লাগতে পারে।

কৌশল: Strong Induction

Base case: \(P(n_0)\) সত্য দেখাও।

Strong inductive step: ধরো \(P(n_0), P(n_0+1), \ldots, P(k)\) সব সত্য (যেকোনো \(k \geq n_0\)-এর জন্য)। এই ধারণা থেকে দেখাও \(P(k+1)\) সত্য।

উদাহরণ — উপপাদ্য ৫ (Fundamental Theorem of Arithmetic-এর একটা অংশ): প্রতিটা পূর্ণসংখ্যা \(n \geq 2\) মৌলিক (prime) বা মৌলিক সংখ্যাদের গুণফল।

প্রমাণ (strong induction):

Base case (\(n = 2\)): \(2\) নিজেই মৌলিক। ✓

Inductive step: ধরো \(2, 3, \ldots, k\) সব ক্ষেত্রে সত্য। দেখাতে হবে \(k+1\)-এর জন্য।

যদি \(k+1\) মৌলিক হয়: তাহলে সরাসরি সত্য।
যদি \(k+1\) মৌলিক না হয়: তাহলে \(k+1 = a \cdot b\) যেখানে \(2 \leq a, b < k+1\)। Inductive hypothesis অনুযায়ী \(a\) এবং \(b\) উভয়ই মৌলিক বা মৌলিকদের গুণফল। তাই তাদের গুণফল \(k+1\)-ও মৌলিকদের গুণফল। \(\blacksquare\)

(এখানে \(a < k+1\) এবং \(b < k+1\) — এজন্যই strong induction দরকার, শুধু \(P(k)\) দিয়ে হতো না।)

৩.৬ — Disproof by Counterexample (প্রতিউদাহরণ দিয়ে খণ্ডন)¶

কৌশল: Counterexample

"সব \(x\)-এর জন্য \(P(x)\)" ধরনের দাবি খণ্ডন করতে একটামাত্র \(x\) খুঁজে বের করো যার জন্য \(P(x)\) মিথ্যা। সেটাই counterexample (প্রতিউদাহরণ)।

কেন কাজ করে? কারণ \(\neg(\forall x\, P(x)) \equiv \exists x\, \neg P(x)\) (0.1-এ প্রমাণিত)।

উদাহরণ: "সব মৌলিক সংখ্যা বিজোড়।"

Counterexample: \(2\) একটা মৌলিক সংখ্যা কিন্তু জোড়। ✓ দাবি খণ্ডিত।

উদাহরণ ২: "সব \(n\)-এর জন্য \(n^2 + n + 41\) মৌলিক।"

(এটা \(n = 0\) থেকে \(n = 39\) পর্যন্ত সত্য — কিন্তু সবসময় সত্য নয়।)

Counterexample: \(n = 40\) নাও।

\[40^2 + 40 + 41 = 1600 + 40 + 41 = 1681 = 41 \times 41\]

\(1681\) মৌলিক নয়। তাই দাবি মিথ্যা। \(\blacksquare\)

৪. উদাহরণ ও Analogy¶

Analogy — একটা রহস্যের তদন্ত¶

Proof-এর কৌশলগুলোকে একটা গোয়েন্দার তদন্তের সাথে মেলাও:

তদন্তের পদ্ধতি	Proof-এর কৌশল
সরাসরি ঘটনার সাক্ষী খোঁজো	Direct proof
"আলিবাই না থাকলে দোষী" (উল্টো থেকে ধরো)	Contrapositive
"যদি সে নির্দোষ হতো, তাহলে এটা সম্ভব হতো না"	Contradiction
"প্রথম ঘটনায় এই pattern, তারপর একইভাবে চলছে..."	Induction
"একটা মাত্র ব্যতিক্রম পাওয়া গেছে — দাবি মিথ্যা"	Counterexample

Worked Example: Contradiction দিয়ে একটা সহজ প্রমাণ¶

দাবি: কোনো বৃহত্তম মৌলিক সংখ্যা নেই (infinitely many primes আছে — Euclid-এর ক্লাসিক)।

প্রমাণ (contradiction):

ধরো বৃহত্তম মৌলিক সংখ্যা আছে। মানে সমস্ত মৌলিক সংখ্যার তালিকা সীমিত: \(p_1, p_2, \ldots, p_n\)।

গড়ো \(N = p_1 \cdot p_2 \cdots p_n + 1\)।

লক্ষ্য করো: \(N\)-কে \(p_1\) দিয়ে ভাগ দিলে ভাগশেষ \(1\)। একইভাবে \(p_2, \ldots, p_n\) কারো দ্বারা ভাগ যায় না।

কিন্তু প্রতিটা সংখ্যার কোনো না কোনো মৌলিক উৎপাদক থাকে — তাহলে \(N\)-এর মৌলিক উৎপাদক কোনোটাই তালিকায় নেই! তাহলে তালিকা সম্পূর্ণ নয় — contradiction।

উপসংহার: মৌলিক সংখ্যার কোনো শেষ নেই। \(\blacksquare\)

৫. সাধারণ ভুল (Common mistakes)¶

Converse-কে মূলের সমান ভাবা। "\(n^2\) জোড় \(\Rightarrow\) \(n\) জোড়" সত্য, কিন্তু সব theorem-এর converse সত্য নয়। 0.1-এ দেখা গেছে \(p \to q \not\equiv q \to p\)।
Induction-এ base case বাদ দেওয়া। Base case ছাড়া inductive step অর্থহীন — ডমিনোর শিকলে প্রথমটা না ফেললে পরেরগুলো কখনোই পড়বে না।
Contradiction-এ কোথায় contradiction সেটা স্পষ্ট না করা। "এটা ভুল কারণ contradiction" বললে হবে না — কোন দুটো statement একসাথে সত্য হতে পারে না সেটা সুস্পষ্টভাবে দেখাতে হবে।
Inductive step-এ যা প্রমাণ করতে হবে সেটাই ধরে নেওয়া। এটাকে বলে circular reasoning (বৃত্তাকার যুক্তি)। ধরা যায় শুধু \(P(k)\) (inductive hypothesis), ধরা যায় না \(P(k+1)\)।
Counterexample আর proof এক ভাবা। Counterexample শুধু একটা দাবি ভাঙতে পারে, প্রমাণ করতে পারে না। "সব জোড় সংখ্যার উদাহরণ: \(4, 6, 8\)" — এটা "সব জোড় সংখ্যা বিভাজ্য \(2\) দিয়ে"-র proof নয়।
\(\sqrt{2}\) proof-এ "সরলীকৃত" ধারণা না নেওয়া। তাহলে \(p\) আর \(q\) উভয়ই জোড় হওয়া contradiction হতো না — আরো ভাগ করতে থাকা যেত।
Strong induction কখন দরকার সেটা না বোঝা। যদি \(P(k+1)\) প্রমাণ করতে শুধু \(P(k)\) নয়, আরো আগের কিছু ফলাফল লাগে — তখনই strong induction।

৬. এক্সারসাইজ (Exercises)¶

নিজে চেষ্টা করো, তারপর সমাধান খোলো।

Direct proof: দেখাও যে দুটো বিজোড় সংখ্যার যোগফল সবসময় জোড়।
Direct proof: দেখাও যে যদি \(a\) এবং \(b\) উভয়ই জোড় পূর্ণসংখ্যা হয়, তাহলে \(ab\) চার দিয়ে বিভাজ্য।
Contrapositive: দেখাও — যদি \(n^3\) জোড় হয়, তাহলে \(n\) জোড়।
Contradiction: দেখাও \(\sqrt{3}\) অমূলদ।
Induction: দেখাও: সব \(n \geq 1\)-এর জন্য \(\displaystyle\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}\)।
Induction: দেখাও: সব \(n \geq 1\)-এর জন্য \(2^n > n\)।
Counterexample: নিচের দাবিগুলো সত্য না মিথ্যা? মিথ্যা হলে counterexample দাও।
(ক) "সব \(n \geq 1\)-এর জন্য \(2^n + 1\) মৌলিক।"
(খ) "যদি \(n^2\) বিজোড়, তবে \(n\) বিজোড়।"
(গ) "সব বাস্তব \(x\)-এর জন্য \(x^2 \geq x\)।"
সব কৌশল মিলিয়ে: নিচের দাবিটা সত্য না মিথ্যা? উত্তর দাও ও প্রমাণ বা counterexample দাও: "যদি \(a \cdot b\) জোড় হয়, তবে \(a\) জোড় এবং \(b\) জোড়।"

৭. সমাধান (ব্যাখ্যাসহ)¶

১-নং সমাধান দেখাও

দাবি: দুটো বিজোড় সংখ্যার যোগফল জোড়।

প্রমাণ (direct):

ধরো \(a\) এবং \(b\) বিজোড়। তাহলে সংজ্ঞা অনুযায়ী \(a = 2m+1\) এবং \(b = 2n+1\) কোনো পূর্ণসংখ্যা \(m, n\)-এর জন্য।

\[a + b = (2m+1) + (2n+1) = 2m + 2n + 2 = 2(m+n+1)\]

\(m+n+1\) একটা পূর্ণসংখ্যা। তাই \(a+b = 2 \times (\text{পূর্ণসংখ্যা})\), অর্থাৎ জোড়। \(\blacksquare\)

২-নং সমাধান দেখাও

দাবি: \(a, b\) জোড় হলে \(ab\) চার দিয়ে বিভাজ্য।

প্রমাণ (direct):

\(a = 2m\), \(b = 2n\) (কারণ উভয়ই জোড়)।

\[ab = (2m)(2n) = 4mn\]

\(mn\) পূর্ণসংখ্যা, তাই \(ab = 4 \times mn\) — চার দিয়ে বিভাজ্য। \(\blacksquare\)

৩-নং সমাধান দেখাও

দাবি: \(n^3\) জোড় \(\Rightarrow\) \(n\) জোড়।

Contrapositive নিই: "\(n\) বিজোড় \(\Rightarrow\) \(n^3\) বিজোড়।"

প্রমাণ:

ধরো \(n = 2k+1\)।

\[n^3 = (2k+1)^3 = 8k^3 + 12k^2 + 6k + 1 = 2(4k^3 + 6k^2 + 3k) + 1\]

এটা বিজোড়। তাই contrapositive সত্য, অর্থাৎ মূল দাবিও সত্য। \(\blacksquare\)

কেন contrapositive বেছে নিলাম? "\(n^3\) জোড়" ধরে সরাসরি \(n\) জোড় দেখানো কঠিন — ঘনমূলের সাথে মোকাবিলা করতে হতো। Contrapositive-এ \(n\) জোড়/বিজোড় ধরে \(n^3\) জোড়/বিজোড় দেখানো অনেক সহজ।

৪-নং সমাধান দেখাও

দাবি: \(\sqrt{3}\) অমূলদ।

প্রমাণ (contradiction): \(\sqrt{2}\)-এর মতোই কাঠামো।

ধরো \(\sqrt{3} = \frac{p}{q}\) সরলীকৃত আকারে (অর্থাৎ \(\gcd(p,q)=1\))।

\[3 = \frac{p^2}{q^2} \implies p^2 = 3q^2\]

তাই \(p^2\) তিন দিয়ে বিভাজ্য। একটু চিন্তা করলে দেখা যায়: যদি \(3 \mid p^2\) তবে \(3 \mid p\) (কারণ \(3\) মৌলিক — Euclid's lemma)।

তাহলে \(p = 3m\):

\[(3m)^2 = 3q^2 \implies 9m^2 = 3q^2 \implies q^2 = 3m^2\]

তাই \(q\)-ও তিন দিয়ে বিভাজ্য।

কিন্তু তাহলে \(3 \mid p\) এবং \(3 \mid q\) — \(\gcd(p,q) \geq 3\), যা সরলীকৃত অনুমানের বিরুদ্ধে। Contradiction।

উপসংহার: \(\sqrt{3}\) অমূলদ। \(\blacksquare\)

৫-নং সমাধান দেখাও

দাবি: \(\displaystyle\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}\)।

প্রমাণ (induction):

Base case (\(n=1\)):

\[\text{বাঁয়ে: } 1^2 = 1 \qquad \text{ডানে: } \frac{1 \cdot 2 \cdot 3}{6} = 1 \checkmark\]

Inductive step: ধরো \(n=m\)-এর জন্য সত্য:

\[\sum_{k=1}^{m} k^2 = \frac{m(m+1)(2m+1)}{6}\]

\(n = m+1\)-এর জন্য দেখাই:

\[\sum_{k=1}^{m+1} k^2 = \underbrace{\sum_{k=1}^{m} k^2}_{=\frac{m(m+1)(2m+1)}{6}} + (m+1)^2\]

\[= \frac{m(m+1)(2m+1)}{6} + (m+1)^2 = (m+1)\left[\frac{m(2m+1)}{6} + (m+1)\right]\]

\[= (m+1) \cdot \frac{m(2m+1) + 6(m+1)}{6} = (m+1) \cdot \frac{2m^2 + 7m + 6}{6}\]

\[= (m+1) \cdot \frac{(m+2)(2m+3)}{6} = \frac{(m+1)(m+2)(2m+3)}{6}\]

এটাই \(n = m+1\)-এর ক্ষেত্রে সূত্র: \(\dfrac{(m+1)((m+1)+1)(2(m+1)+1)}{6}\)। \(\blacksquare\)

৬-নং সমাধান দেখাও

দাবি: সব \(n \geq 1\)-এর জন্য \(2^n > n\)।

প্রমাণ (induction):

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

Inductive step: ধরো \(2^k > k\)।

\[2^{k+1} = 2 \cdot 2^k > 2k = k + k \geq k + 1\]

(শেষে \(k \geq 1\) ব্যবহার করলাম, তাই \(k \geq 1\)।)

তাই \(2^{k+1} > k+1\)। \(\blacksquare\)

৭-নং সমাধান দেখাও

(ক) "\(2^n + 1\) সবসময় মৌলিক" — মিথ্যা।

Counterexample: \(n = 3\)।

\[2^3 + 1 = 9 = 3 \times 3\]

\(9\) মৌলিক নয়। দাবি খণ্ডিত।

(খ) "\(n^2\) বিজোড় হলে \(n\) বিজোড়" — সত্য।

এটা উপপাদ্য ২ (contrapositive দিয়ে প্রমাণিত)। কোনো counterexample নেই।

(গ) "সব বাস্তব \(x\)-এর জন্য \(x^2 \geq x\)" — মিথ্যা।

Counterexample: \(x = \frac{1}{2}\)।

\[\left(\tfrac{1}{2}\right)^2 = \tfrac{1}{4} < \tfrac{1}{2}\]

তাই \(x^2 < x\)। দাবি খণ্ডিত।

(আরও উদাহরণ: \(x = 0.7\): \(0.49 < 0.7\)।)

৮-নং সমাধান দেখাও

দাবি: "\(ab\) জোড় \(\Rightarrow\) \(a\) জোড় এবং \(b\) জোড়।"

এটা মিথ্যা।

Counterexample: \(a = 2\), \(b = 3\)।

\[ab = 6 \text{ (জোড়)}\]

কিন্তু \(b = 3\) বিজোড়।

তাই "\(ab\) জোড়" হলে এটা অনুসরণ করে না যে উভয়ই জোড়।

সঠিক বক্তব্য হবে: "\(ab\) জোড় \(\Rightarrow\) \(a\) জোড় বা \(b\) জোড়" — এটা সত্য। কারণ যদি \(a\) এবং \(b\) উভয়ই বিজোড় হতো, তাহলে তাদের গুণফলও বিজোড় হতো (দুটো বিজোড়ের গুণফল বিজোড় — সহজে direct proof করা যায়)।

৮. সারসংক্ষেপ ও Checklist¶

এই অধ্যায়ের পর নিজেকে যাচাই করো:

[ ] Proof কী — সংজ্ঞা, axiom ও পূর্বের theorem থেকে শুরু করে পদে পদে logic-এর শিকল।
[ ] Direct proof: \(P\) ধরো, \(Q\) দেখাও — সবচেয়ে সরল কৌশল।
[ ] Contrapositive: \(p \to q \equiv \neg q \to \neg p\) (0.1-এর ফলাফল) — কখন ব্যবহার করব সেটা বুঝি।
[ ] Contradiction: \(\neg Q\) ধরো, অসঙ্গতিতে পৌঁছাও — এবং সেই অসঙ্গতি স্পষ্টভাবে দেখাতে পারি।
[ ] \(\sqrt{2}\) অমূলদ — এই classic প্রমাণটা মুখস্থ নয়, বুঝে বলতে পারি।
[ ] Mathematical Induction: base case + inductive step — দুটো অংশই কেন দরকার জানি।
[ ] Strong induction: কখন সাধারণ induction-এর জায়গায় strong দরকার সেটা বুঝি।
[ ] Counterexample: একটা "সব"-দাবি ভাঙতে একটামাত্র উদাহরণ যথেষ্ট; কিন্তু প্রমাণ করতে যথেষ্ট নয়।
[ ] সমস্যা দেখে কোন কৌশল বেছে নেব সেই intuition গড়তে শুরু করেছি।

➡️ পরের অধ্যায়: 0.5 — সংখ্যা পদ্ধতি (Number Systems ℕ, ℤ, ℚ, ℝ) — এখন যে proof-কৌশলগুলো শিখলাম সেগুলো দিয়েই দেখব ℕ, ℤ, ℚ, ℝ-এর গুণাগুণ কীভাবে প্রমাণ করা হয়।