গাণিতিক আরোহ পদ্ধতি
গাণিতিক আরোহ পদ্ধতি (mathematical induction) গণিতে প্রমাণের একটি বহুল ব্যবহৃত পদ্ধতি। এটি সবচেয়ে বেশি ব্যবহৃত হয়, যখন আমরা স্বাভাবিক সংখ্যা বা অন্য কোনো অনুক্রম নিয়ে কাজ করি।
নীতি
মূল নীতি হলো, প্রদত্ত বিবৃতিটি আমরা প্রথমে কোনো প্রথম উপাদানের জন্য প্রমাণ করি। স্বাভাবিক সংখ্যার ক্ষেত্রে এটি সাধারণত n = 1। এটি প্রমাণ করা হয় সরাসরি মান বসিয়ে। পরের ধাপে, অর্থাৎ আরোহ ধাপে, আমরা এই শর্তযুক্ত উক্তিটি প্রমাণ করি: “যদি বিবৃতিটি n = a এর জন্য সত্য হয়, তবে এটি n = a + 1 এর জন্যও সত্য”।
এই দুইটি ধাপ থেকে আমরা সিদ্ধান্তে আসতে পারি যে প্রদত্ত রাশিটি সব n এর জন্য সত্য (যে সেট নিয়ে আমরা কাজ করছি, তার মধ্যে)। এমন কেন হয়? শুরুতে আমরা প্রমাণ করি যে রাশিটি n = 1 এর জন্য সত্য। একই সঙ্গে আমরা জানি, রাশিটি n = a এর জন্য সত্য হলে n = a + 1 এর জন্যও সত্য। তাই a = 1 নিই। আমরা জানি, a = 1 এর জন্য রাশিটি সত্য, আর এটাও জানি যে এটি a + 1 = 2 এর জন্য সত্য। এখন আমরা জানি, রাশিটি a = 2 এর জন্য সত্য। কিন্তু যেহেতু এটি a + 1 এর জন্যও সত্য, তাই এটি 2 + 1 = 3 এর জন্যও সত্য হতে হবে। এভাবে চলতে থাকে।
প্রথম উদাহরণ
প্রথম উদাহরণটি হবে তুচ্ছ। আমরা প্রমাণ করব, যেকোনো জোড় সংখ্যার সঙ্গে দুই যোগ করলে আবার একটি জোড় সংখ্যা পাওয়া যায়। যেহেতু আমরা স্বাভাবিক সংখ্যা নিয়ে কাজ করছি, তাই সাধারণভাবে জোড় সংখ্যাকে লিখি 2n, যেখানে n একটি স্বাভাবিক সংখ্যা। n এর স্থলে যেকোনো স্বাভাবিক সংখ্যা বসালে ফলাফল হিসেবে একটি জোড় সংখ্যা পাওয়া যায়, তা প্রথম দেখাতেই বোঝা যায়। বিভাজ্যতা লেখা হয় একটি খাড়া রেখা দিয়ে, এভাবে:
এই লেখার অর্থ, দুই রাশি 2n কে নিঃশেষে ভাগ করে। বিভাজ্যতা লিখতে যখন পারি, তখন গাণিতিক আরোহ পদ্ধতিতে আমাদের যা প্রমাণ করতে হবে, তাও লিখতে পারি।
প্রথম উদাহরণে আমাদের এটিই প্রমাণ করতে হবে, অর্থাৎ দুই রাশি 2n + 2 কে ভাগ করে। এটি হুবহু মূল কথায় দেওয়া প্রশ্নের সঙ্গে মিলে যায়: “যেকোনো জোড় সংখ্যার সঙ্গে দুই যোগ করলে আবার একটি জোড় সংখ্যা পাওয়া যায়”।
আরোহ পদ্ধতির প্রথম ধাপে আমরা এটি প্রথম উপাদানের জন্য, অর্থাৎ একের জন্য প্রমাণ করি। রাশিতে n = 1 বসাই:
দুই চারকে নিঃশেষে ভাগ করে, তাই প্রথম উপাদানের জন্য এটি সত্য। এরপর আসে আরোহ ধাপ, যেখানে আমাদের প্রমাণ করতে হবে যে এটি a তম উপাদানের জন্য সত্য হলে (a + 1) তম উপাদানের জন্যও সত্য। শুরুতে ধরে নিই যে আমাদের অনুমানটি সত্য, অর্থাৎ n = a:
এই রাশিটিকে আমরা সত্য বলে ধরে নিচ্ছি। প্রমাণ গঠনে আমরা এটি ব্যবহার করব। এখন আমরা প্রমাণ করতে চাই যে
আমরা কী করলাম? a এর জায়গায় লিখলাম (a + 1)। বন্ধনীগুলো গুরুত্বপূর্ণ। এই রাশিটি ভুল হতো: 2a + 1 + 2। আমরা পুরো রাশির সঙ্গে এক যোগ করছি না, বরং সত্যিই a কে এক বেশি করছি, অর্থাৎ (a + 1)। গুণ করে বন্ধনী খুলে রাশিটি রূপান্তর করি।
এখন বিভাজ্যতা নিয়ে একটু অন্য প্রসঙ্গ। ধরা যাক, দুইটি সংখ্যা, যেমন p ও q, কোনো একটি সংখ্যা, যেমন r দ্বারা বিভাজ্য। তাহলে তাদের যোগফলও সংখ্যা r দ্বারা বিভাজ্য। অর্থাৎ:
যেমন, সংখ্যাগুলো p = 8, q = 20 এবং r = 4 বসাতে পারি। দেখা যাচ্ছে, চার আট ও বিশ দুইটিকেই ভাগ করে। আর একইভাবে তাদের যোগফল 8 + 20 = 28 কেও ভাগ করে।
আমাদের উদাহরণে এটি কীভাবে কাজে লাগাব? ডানপক্ষকে p ও q সংখ্যায় এভাবে ভাগ করি:
সংখ্যা q, অর্থাৎ দুই, স্পষ্টতই দুই দ্বারা বিভাজ্য। আর p রাশিটিও দুই দ্বারা বিভাজ্য, কারণ অনুমান আমাদের তা-ই বলে। রাশি p হুবহু আমাদের অনুমানের সঙ্গে মিলে যায়, যাকে আমরা সত্য বলে ধরে নিয়েছি। আর p দুই দ্বারা বিভাজ্য এবং একই সঙ্গে q দুই দ্বারা বিভাজ্য হলে তাদের যোগফলও দুই দ্বারা বিভাজ্য।
অনুমানটি নিয়ে আরেকবার বলি। শুরুতে আমরা বলেছিলাম, আমরা ধরে নিচ্ছি যে
তাই প্রমাণ গঠনের সময় যখন 2a + 2 রাশিটি পেলাম, তখন বলতে পারলাম যে এটি দুই দ্বারা বিভাজ্য, কারণ এটিই আমাদের অনুমান। গাণিতিক আরোহ পদ্ধতির এটিই সাধারণত সবচেয়ে কঠিন ধাপ: কখন এবং কেন আরোহ অনুমান ব্যবহার করা যায়, তা বোঝা।
এখানেই আরোহ শেষ, প্রমাণ সফলভাবে সম্পন্ন হলো, উপপাদ্যটি সত্য।
চাইলে তুমি অন্যভাবেও ভাঙতে পার, তখন অনুমান ব্যবহার করতে হবে না: p = 2n এবং q = 2 + 2। সংখ্যা q = 4 স্পষ্টতই দুই দ্বারা বিভাজ্য, আর একইভাবে p = 2n রাশিটিও, কারণ দুই দিয়ে ভাগ করলে থাকে সংখ্যা n, যা স্বাভাবিক, অর্থাৎ পূর্ণ সংখ্যা। আবার আমরা এমন দুইটি রাশি পেলাম, যারা দুইটিই দুই দ্বারা বিভাজ্য, তাই তাদের যোগফলও দুই দ্বারা বিভাজ্য।
তবে দুই ক্ষেত্রেই আমরা প্রমাণ করেছি যে
- প্রদত্ত রাশিটি n = 1 এর জন্য সত্য,
- রাশিটি n এর জন্য সত্য হলে n + 1 এর জন্যও সত্য।
এখান থেকে আমরা সিদ্ধান্তে আসতে পারি:
- আমরা জানি, রাশিটি n = 1 এর জন্য সত্য।
- এটি n এর জন্য সত্য হলে n + 1 এর জন্যও সত্য হতে হবে, অর্থাৎ 1 + 1 এর জন্যও, অর্থাৎ রাশিটি n = 2 এর জন্যও সত্য।
- এটি n এর জন্য সত্য হলে n + 1 এর জন্যও সত্য হতে হবে, অর্থাৎ 2 + 1 এর জন্যও, অর্থাৎ রাশিটি n = 3 এর জন্যও সত্য।
- এটি n এর জন্য সত্য হলে n + 1 এর জন্যও সত্য হতে হবে, অর্থাৎ 3 + 1 এর জন্যও, অর্থাৎ রাশিটি n = 4 এর জন্যও সত্য।
- এটি n এর জন্য সত্য হলে n + 1 এর জন্যও সত্য হতে হবে, অর্থাৎ 4 + 1 এর জন্যও, অর্থাৎ রাশিটি n = 5 এর জন্যও সত্য।
- …
দ্বিতীয় উদাহরণ
এবার গাণিতিক আরোহ পদ্ধতিতে একটি সহজ বিবৃতি প্রমাণ করি:
প্রথমে ভিত্তি ধাপ: বের করি বিবৃতিটি n = 1 এর জন্য সত্য কি না। এটি স্বাভাবিক সংখ্যার প্রথম উপাদান, যেখান থেকে আমরা n বেছে নিই।
এটি স্পষ্টতই সত্য। এখন আরোহ ধাপে যাই। এখানে আমাদের বের করতে হবে, বিবৃতিটি n = a এর জন্য সত্য হলে n = a + 1 এর জন্যও সত্য কি না। তাই আমাদের অনুমান হলো
এবং আমরা প্রমাণ করতে চাই:
প্রথমে বামপক্ষকে ঘাতের নিয়ম অনুযায়ী ভেঙে লিখি, আর ডানপক্ষে শুধু গুণ করে বন্ধনী খুলি।
বামপক্ষে গুণের বদলে যোগ ব্যবহার করি, ডানপক্ষ অপরিবর্তিত রাখি।
এখন অনুমানটি কাজে লাগাই। অনুমান হলো এমন একটি উক্তি, যাকে আমরা সত্য বলে ধরে নিই। অসমতার দুই পক্ষেই যোগফল আকারে দুইটি করে রাশি আছে। আবার একই সঙ্গে আমরা জানি যে
প্রথম সারিটি আমাদের অনুমান বলে, আর দ্বিতীয় উক্তিটি তুচ্ছ (2a এর ক্ষুদ্রতম মান a = 1 এর জন্য, আর তা দুইয়ের সমান)। অতএব আমরা জানি, বামপক্ষের দুইটি রাশির প্রত্যেকটি ডানপক্ষের সংশ্লিষ্ট রাশির চেয়ে বড় বা সমান। এভাবে আরোহ পদ্ধতিতে প্রমাণিত হলো যে রাশিটি a এর জন্য সত্য হলে (a + 1) এর জন্যও সত্য। আর যেহেতু রাশিটি একের জন্যও সত্য, তাই প্রদত্ত রাশিটি সত্য।
তৃতীয় উদাহরণ
চল, এই বিবৃতিটি প্রমাণ করার চেষ্টা করি:
কথায়: n তিন দ্বারা বিভাজ্য হলে n2 সংখ্যাটিও তিন দ্বারা বিভাজ্য। n তিন দ্বারা বিভাজ্য না হলে রাশিটি স্পষ্টতই সত্য (শর্তযুক্ত উক্তির সংজ্ঞা অনুযায়ী)। তাই আমরা কেবল সেই ক্ষেত্রগুলো দেখব, যেখানে n তিন দ্বারা বিভাজ্য। এতে আমরা স্বাভাবিক সংখ্যার একটি অনুক্রম পাই: ai=3, 6, 9, 12, 15… এখন থেকে আমরা এই অনুক্রম ai এর মধ্যেই কাজ করব।
আরোহ পদ্ধতিতে প্রমাণ শুরু করি ভিত্তি ধাপ দিয়ে, অর্থাৎ এটি প্রথম উপাদানের জন্য সত্য কি না। মনে করিয়ে দিই, আমরা অনুক্রম ai এর মধ্যে কাজ করছি, তাই এই অনুক্রমের প্রথম উপাদানটি নিই, অর্থাৎ উপাদান a1, যা তিন। তিনের জন্য রাশিটি সত্য:
এখন আরোহ ধাপে যাই। আমরা দেখছি, অনুক্রম ai কে লেখা যায় 3n আকারে, যেখানে n একটি স্বাভাবিক সংখ্যা। অর্থাৎ দ্বিতীয় উপাদান আগেরটির চেয়ে তিন বেশি, ইত্যাদি। এখন ধরে নিই যে রাশিটি n এর জন্য সত্য, আর আমাদের নিশ্চিত করতে হবে যে এটি (n + 3) এর জন্যও সত্য। এই রাশিটিই আমরা যে অনুক্রমে কাজ করছি, তার পরের উপাদানটি দেয়। প্রথমে অনুমানটি লিখি:
আর তারপর যা প্রমাণ করতে চাই
সূত্রের সাহায্যে অন্য পাশের বন্ধনীটি খুলি:
আমরা প্রায় লক্ষ্যে পৌঁছে গেছি। বাম পাশে আছে এমন একটি রাশি, যা অবশ্যই তিন দ্বারা বিভাজ্য, কারণ অনুমান অনুযায়ী n তিন দ্বারা বিভাজ্য (আমরা কেবল অনুক্রম ai এর সংখ্যা নিয়ে কাজ করছি), আর তিনও তিন দ্বারা বিভাজ্য। ডান পাশে প্রথমে আছে n2, যা অনুমান অনুযায়ী তিন দ্বারা বিভাজ্য। কারণ আমরা জানি n তিন দ্বারা বিভাজ্য, আর অনুমান বলে, n তিন দ্বারা বিভাজ্য হলে n2 সংখ্যাটিও তিন দ্বারা বিভাজ্য:
এরপর আসে রাশি 6n, যা স্পষ্টতই তিন দ্বারা বিভাজ্য। একে ভগ্নাংশ লঘিষ্ঠকরণ হিসেবে কল্পনা করতে পার:
চলক n কোনো একটি স্বাভাবিক সংখ্যা, তাই 2n গুণফলটিও একটি স্বাভাবিক সংখ্যা হবে। অর্থাৎ তিন দিয়ে ভাগ করে আমরা একটি স্বাভাবিক সংখ্যা পেয়েছি, তাই রাশি 6n অবশ্যই তিন দ্বারা বিভাজ্য। আর শেষের নয়ও আবার তিন দ্বারা বিভাজ্য। রাশিটি প্রথম উপাদানের জন্য এবং আরোহ ধাপেও সত্য, অতএব এটি সত্য।
রাশিতে বন্ধনীর সংখ্যা
শেষ উদাহরণটি একটু ব্যতিক্রমী হবে। আমরা প্রমাণ করার চেষ্টা করব যে একটি সরল রাশিতে বন্ধনীর সংখ্যা সবসময় জোড়। এতে তুমি দেখবে, গাণিতিক আরোহ পদ্ধতি শুধু স্বাভাবিক সংখ্যা নয়, একেবারে ভিন্ন প্রেক্ষাপটেও ব্যবহার করা যায়। শুরুতে আমাদের সংজ্ঞায়িত করতে হবে, সরল রাশি কী। সরল রাশি হলো:
- একটি স্বাভাবিক সংখ্যা,
- p একটি সরল রাশি হলে (p2) রাশিটিও সরল রাশি,
- p ও q সরল রাশি হলে (p + q) রাশিটিও সরল রাশি।
তাহলে সরল রাশি কোনগুলো: 12, 54, (5 + 6), (12 + 7), (62), ((5 + 6)2)। অন্যদিকে এগুলো সরল রাশি নয়:
- 1 + 2 → বাইরের বন্ধনী নেই,
- (1 + 2 → ডান বন্ধনী নেই,
- 132 → বাইরের বন্ধনী নেই,
- (1 + 2 + 3) → বন্ধনী নেই, সঠিক লেখা হতো (1 + (2 + 3))
একটি সরল রাশি তৈরি হতে পারে, যেমন, এভাবে। শুরুতে বেছে নিই সরল রাশি (a + b)। এখন a এর স্থলে বসাই সরল রাশি a = (c + d), ফলে পাই ((c + d) + b), আর b এর স্থলে বসাই তিন: ((c + d) + 3)। c এর স্থলে বসাই দশ: ((10 + d) + 3), আর শেষে d এর স্থলে বসাই (52): ((10 + (52)) + 3)। বন্ধনীগুলো ঠিকঠাক রাখা জরুরি, নইলে এটি কাজ করবে না।
এখন প্রমাণ করব যে সরল রাশিতে জোড় সংখ্যক বন্ধনী থাকে (শূন্যও জোড় সংখ্যা)।
আরোহ পদ্ধতির প্রথম ধাপে আমরা একটি প্রথম উপাদান বেছে নিই। এক্ষেত্রে প্রথম উপাদান হবে সবচেয়ে তুচ্ছ সরল রাশি, অর্থাৎ যেকোনো স্বাভাবিক সংখ্যা। তাই ধরি
রাশি j তে বন্ধনীর সংখ্যা শূন্য, অর্থাৎ প্রথম উপাদান শর্ত পূরণ করে। আরোহ ধাপে আমরা ধরে নেব, আমাদের কাছে দুইটি সরল রাশি p ও q আছে এবং দুইটিতেই জোড় সংখ্যক বন্ধনী আছে। তাহলে আমাদের প্রমাণ করতে হবে যে সরল রাশি (p + q) ও (p2) তেও জোড় সংখ্যক বন্ধনী আছে।
প্রথমে যোগ। একটি ফাংশন z(q) সংজ্ঞায়িত করি, যা রাশি q এর বন্ধনীর সংখ্যা দেয়। তাহলে রাশি (p + q) তে আছে z(p) + z(q) + 2 টি বন্ধনী। অর্থাৎ p ও q রাশির বন্ধনীর যোগফলের চেয়ে এতে দুইটি বন্ধনী বেশি। অনুমান অনুযায়ী z(p) ও z(q) দুইটিই জোড়, তাই তিনটি জোড় সংখ্যা যোগ করলে আবার জোড় সংখ্যা পাই। এই ক্ষেত্রে উক্তিটি সত্য।
এবার ঘাত। আবার অনুমানটি সত্য যে সরল রাশি p তে জোড় সংখ্যক বন্ধনী আছে। তাহলে রাশি (p2) তে আছে z(p) + 2 টি বন্ধনী, অর্থাৎ আবার রাশি p এর চেয়ে দুইটি বন্ধনী বেশি। এক্ষেত্রেও আমরা জোড় সংখ্যা যোগ করছি, তাই ফলাফল জোড়।
উক্তিটি প্রথম উপাদানের জন্য সত্য এবং আরোহ ধাপেও সত্য, তাই উক্তিটি সত্য।
সূচিপত্র: প্রমাণ কী, বিরোধের মাধ্যমে প্রমাণ, গাণিতিক আরোহ পদ্ধতি