পাঠ ৩০ · ৪৪-এর মধ্যে · মডিউল ৬
Home / Courses / Discrete Mathematics / ক্যারেক্টারিস্টিক ইকুয়েশন

রিকারেন্স সমাধান — ক্যারেক্টারিস্টিক ইকুয়েশন পদ্ধতি

Solving recurrences — the characteristic equation method
৯ মিনিট পড়া মধ্যবর্তী · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

এই পাঠে যা শিখবেন

  • দ্বিতীয়-ক্রম লিনিয়ার হোমোজিনিয়াস রিকারেন্স থেকে ক্যারেক্টারিস্টিক ইকুয়েশন কীভাবে তৈরি হয়
  • ভিন্ন বাস্তব মূলের (distinct real roots) ক্ষেত্রে সম্পূর্ণ সমাধান পদ্ধতি — ধাপে ধাপে
  • বেস কেস ব্যবহার করে সাধারণ সমাধানের অজানা ধ্রুবক $A, B$ বের করা
  • পুনরাবৃত্ত মূলের (repeated root) ক্ষেত্রে সমাধানের ভিন্ন রূপ

১ · ক্যারেক্টারিস্টিক ইকুয়েশন কোথা থেকে আসে?

L29-এ আমরা দেখেছি একটি দ্বিতীয়-ক্রম লিনিয়ার হোমোজিনিয়াস রিকারেন্সের সাধারণ রূপ $a_n = c_1 a_{n-1} + c_2 a_{n-2}$। এই রিকারেন্স সমাধান করার মূল কৌশল হলো — অনুমান করা যে সমাধানটি $a_n = x^n$ আকারের (কোনো ধ্রুবক $x \neq 0$-এর জন্য)। এই অনুমান রিকারেন্সে বসালে —

$$x^n = c_1 x^{n-1} + c_2 x^{n-2}$$

উভয় পাশ $x^{n-2}$ দিয়ে ভাগ করলে (যেহেতু $x \neq 0$) পাওয়া যায় একটি সাধারণ দ্বিঘাত সমীকরণ, যাকে বলা হয় ক্যারেক্টারিস্টিক ইকুয়েশনCharacteristic Equationএকটি লিনিয়ার হোমোজিনিয়াস রিকারেন্সকে $a_n=x^n$ অনুমান করে বসিয়ে পাওয়া বহুপদী সমীকরণ। এর মূলগুলো (roots) দিয়েই রিকারেন্সের সাধারণ সমাধান তৈরি হয়। (characteristic equation) —

$$x^2 = c_1 x + c_2 \quad\Longrightarrow\quad x^2 - c_1 x - c_2 = 0$$

কেন এটি কাজ করে

যদি $x=r$ এই দ্বিঘাত সমীকরণের একটি মূল হয়, তাহলে $a_n = r^n$ সরাসরি মূল রিকারেন্সকে সন্তুষ্ট করে। যেহেতু রিকারেন্সটি লিনিয়ার, তাই দুটি ভিন্ন মূল $r_1, r_2$ থেকে পাওয়া দুটি সমাধানের যেকোনো লিনিয়ার কম্বিনেশন ($A \cdot r_1^n + B \cdot r_2^n$)-ও রিকারেন্সকে সন্তুষ্ট করে। এটিই "সাধারণ সমাধান" (general solution) — বেস কেস প্রয়োগ করে নির্দিষ্ট $A, B$ বের করলেই একমাত্র সঠিক সিকোয়েন্স পাওয়া যায়।

২ · সম্পূর্ণ ওয়ার্কড উদাহরণ

রিকারেন্স: $a_n = a_{n-1} + 2a_{n-2}$, বেস কেস $a_0=0,\ a_1=1$। (এটি ফিবোনাচি নয় — ইচ্ছাকৃতভাবে এমন একটি রিকারেন্স বাছাই করা হয়েছে যার মূলগুলো পরিষ্কার পূর্ণসংখ্যা, ফিবোনাচির মতো অমূলদ "সোনালি অনুপাত" (golden ratio) নয়।)

ধাপ ১ — ক্যারেক্টারিস্টিক ইকুয়েশন লিখুন।

$$x^2 = x + 2 \quad\Longrightarrow\quad x^2 - x - 2 = 0$$

ধাপ ২ — সমীকরণটি ফ্যাক্টর করুন এবং মূল বের করুন।

$$x^2 - x - 2 = (x-2)(x+1) = 0 \quad\Longrightarrow\quad x = 2 \ \text{অথবা}\ x = -1$$

ধাপ ৩ — সাধারণ সমাধান লিখুন (দুটি ভিন্ন বাস্তব মূল)।

$$a_n = A \cdot 2^n + B \cdot (-1)^n$$

ধাপ ৪ — বেস কেস বসিয়ে $A, B$-এর জন্য সমীকরণ তৈরি করুন।

$a_0=0$ বসালে: $A \cdot 2^0 + B \cdot (-1)^0 = A + B = 0$।
$a_1=1$ বসালে: $A \cdot 2^1 + B \cdot (-1)^1 = 2A - B = 1$।

ধাপ ৫ — দুই সমীকরণের সিস্টেম সমাধান করুন।

প্রথম সমীকরণ থেকে $A = -B$। দ্বিতীয় সমীকরণে বসিয়ে: $2(-B) - B = 1 \Rightarrow -3B = 1 \Rightarrow B = -\tfrac{1}{3}$, এবং তাই $A = \tfrac{1}{3}$।

ধাপ ৬ — চূড়ান্ত বদ্ধ-রূপ সূত্র।

$$a_n = \frac{1}{3} \cdot 2^n - \frac{1}{3} \cdot (-1)^n = \frac{2^n - (-1)^n}{3}$$

যাচাই — হাতে ও সূত্র দিয়ে দুইভাবে

মূল রিকারেন্স থেকে: $a_2 = a_1 + 2a_0 = 1 + 2(0) = 1$, এবং $a_3 = a_2 + 2a_1 = 1 + 2(1) = 3$।
বদ্ধ-রূপ সূত্র থেকে: $a_2 = \dfrac{2^2-(-1)^2}{3} = \dfrac{4-1}{3} = 1$ ✓, এবং $a_3 = \dfrac{2^3-(-1)^3}{3} = \dfrac{8-(-1)}{3} = \dfrac{9}{3} = 3$ ✓। দুই পদ্ধতিই একই উত্তর দিচ্ছে।

৩ · পুনরাবৃত্ত মূলের (Repeated Root) ক্ষেত্র

যদি ক্যারেক্টারিস্টিক ইকুয়েশনের মূল দুটি সমান হয় ($r_1 = r_2 = r$), তাহলে $A r^n$ এবং $B r^n$ একই ফাংশন — তাই $A r^n + B r^n$ আসলে একটি মাত্র স্বাধীন ধ্রুবক দেয়, দুটি নয়। এই ক্ষেত্রে সাধারণ সমাধানের রূপ পরিবর্তিত হয়ে হয় —

$$a_n = (A + Bn)\, r^n$$

অর্থাৎ দ্বিতীয় স্বাধীন সমাধানটি $n \cdot r^n$ — একটি অতিরিক্ত $n$ গুণিতক যোগ করে। এই কোর্সে আমরা এই কেসের গভীর ডেরিভেশনে যাব না, তবে মনে রাখা জরুরি: ক্যারেক্টারিস্টিক ইকুয়েশন সমাধান করার পর সবসময় প্রথমে চেক করুন মূলগুলো ভিন্ন কি না — কারণ তার উপরেই নির্ভর করে কোন রূপ ব্যবহার করবেন।

Python
# a_n = a_(n-1) + 2*a_(n-2), a_0=0, a_1=1
# রিকার্সিভ সংজ্ঞা (ইটারেটিভভাবে) বনাম বদ্ধ-রূপ সূত্র — দুটোই মেলাতে হবে

def recurrence_upto(n):
    a = [0, 1]
    for i in range(2, n + 1):
        a.append(a[i - 1] + 2 * a[i - 2])
    return a[:n + 1]

def closed_form(n):
    return (2**n - (-1)**n) // 3  # সবসময় পূর্ণসংখ্যা ফলাফল দেয়

N = 12
recursive_values = recurrence_upto(N)
closed_values = [closed_form(n) for n in range(N + 1)]

print("রিকার্সিভ:", recursive_values)
print("বদ্ধ-রূপ :", closed_values)

for n in range(N + 1):
    assert recursive_values[n] == closed_values[n], f"n={n} তে অমিল!"

print("যাচাই সম্পন্ন — n=0..12 পর্যন্ত সব মান মিলেছে।")

    


    

      কোডে (2**n - (-1)**n) // 3 ব্যবহার করা হয়েছে ভাগশেষহীন পূর্ণসংখ্যা ভাগ (//) দিয়ে, কারণ
      $2^n - (-1)^n$ সবসময় $3$ দ্বারা নিঃশেষে বিভাজ্য (এটি একটি সংখ্যাতাত্ত্বিক তথ্য যা রিকারেন্সের গঠন থেকেই নিশ্চিত) —
      তাই ফলাফল সবসময় একটি পূর্ণসংখ্যা হবে, যেমনটা হওয়া উচিত একটি পূর্ণসংখ্যা সিকোয়েন্সের জন্য।
    


    

      মূল কথা · Key takeaway
      

        ক্যারেক্টারিস্টিক ইকুয়েশন পদ্ধতি একটি রিকার্সিভ সংজ্ঞাকে একটি সরাসরি, বদ্ধ-রূপ সূত্রে রূপান্তর করে — এখন
        $a_{100}$ বের করতে আর ধাপে ধাপে ১০০টি পদ গণনা করতে হবে না, সরাসরি সূত্রে বসিয়ে দিলেই হবে। এই একই কৌশল
        M8/L41-এ নাইভ রিকার্সিভ ফিবোনাচির রানটাইম বিশ্লেষণ করতে সরাসরি ব্যবহার হবে — যেখানে মূলগুলো হবে "সোনালি অনুপাত"
        $\varphi = \frac{1+\sqrt5}{2}$ এবং তার যুগ্ম।
      

    


  


  

    
    
  


  

    
 ভাবনার প্রশ্ন

    
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।


    

      
        প্র ০১
        কেন সমাধান খোঁজার সময় $a_n = x^n$ অনুমান করা হয় — অন্য কোনো রূপ, যেমন $a_n = xn$ বা $a_n=x+n$, কেন কাজ করবে না?
      
      

        

          $a_n=x^n$ অনুমানটি কাজ করে কারণ এটি রিকারেন্সের গঠনের সাথে নিখুঁতভাবে মেলে — রিকারেন্সে প্রতিটি পদ আগের
          পদগুলোর একটি ধ্রুবক-গুণিতক যোগফল, এবং $x^n$-এর একটি বিশেষ ধর্ম আছে: $x^n = x \cdot x^{n-1} = x^2 \cdot x^{n-2}$
          — অর্থাৎ পরবর্তী পদ সবসময় আগের পদের একটি ধ্রুবক গুণিতক। এই ধর্মটিই সমীকরণের উভয় পাশ থেকে $x^{n-2}$ বাতিল
          করে একটি সাধারণ বহুপদী সমীকরণে রূপান্তরিত হতে দেয়। $xn$ বা $x+n$-এর এই ধর্ম নেই — এগুলো বসালে সমীকরণটি
          $n$-নির্ভর থেকে যাবে, একটি নির্দিষ্ট ধ্রুবক সমীকরণে পরিণত হবে না।
        

      

    


    

      
        প্র ০২
        ফিবোনাচি রিকারেন্সেও ঠিক এই একই পদ্ধতি প্রয়োগ করলে কী হবে — কেন এই পাঠে ফিবোনাচির বদলে অন্য একটি রিকারেন্স বেছে নেওয়া হয়েছে?
      
      

        

          ফিবোনাচির ক্যারেক্টারিস্টিক ইকুয়েশন $x^2 - x - 1 = 0$, যার মূল $\dfrac{1 \pm \sqrt5}{2}$ — অর্থাৎ অমূলদ
          (irrational) সংখ্যা। পদ্ধতিটি ঠিক একইভাবে কাজ করে, কিন্তু হাতে-ধাপে-ধাপে দেখানোর জন্য অমূলদ সংখ্যা নিয়ে
          কাজ করা অপ্রয়োজনীয়ভাবে জটিল। তাই এই পাঠে $a_n=a_{n-1}+2a_{n-2}$ বেছে নেওয়া হয়েছে — যার মূল ঠিক $2$ ও $-1$,
          পরিষ্কার পূর্ণসংখ্যা — যাতে মূল পদ্ধতিটির উপর মনোযোগ দেওয়া যায়, জটিল বীজগণিতের উপর নয়।
        

      

    


    

      
        প্র ০৩
        ধাপ ৪-এ কেন $a_0$ ও $a_1$ উভয় বেস কেসই ব্যবহার করতে হলো — শুধু একটি বেস কেস দিয়ে কি $A, B$ বের করা যেত না?
      
      

        

          সাধারণ সমাধানে দুটি অজানা ধ্রুবক আছে — $A$ এবং $B$। বীজগণিতের একটি মৌলিক নিয়ম হলো, দুটি অজানা মান নির্দিষ্টভাবে
          বের করতে দুটি স্বাধীন সমীকরণ প্রয়োজন। এক জোড়া মান ($a_0$) বসালে একটি সমীকরণ পাওয়া যায়, দ্বিতীয় মান ($a_1$)
          বসালে দ্বিতীয় সমীকরণ পাওয়া যায় — তবেই সিস্টেমটি সমাধানযোগ্য হয়ে ওঠে। এটি ঠিক সেই কারণেই — একটি দ্বিতীয়-ক্রম
          (order 2) রিকারেন্সের ঠিক দুটি বেস কেস লাগে, যেমনটি L29-এ আলোচনা হয়েছিল।
        

      

    

  


  

    
 অনুশীলন

    
    
      
  1. 
        হাতে সমাধান করুন: রিকারেন্স $a_n = 5a_{n-1} - 6a_{n-2}$, বেস কেস $a_0=1, a_1=4$-এর ক্যারেক্টারিস্টিক ইকুয়েশন লিখুন, মূল বের করুন, এবং $A, B$ নির্ণয় করে বদ্ধ-রূপ সূত্র বের করুন।
        
    
          
          
    
            
    
              ক্যারেক্টারিস্টিক ইকুয়েশন: $x^2 - 5x + 6 = 0 \Rightarrow (x-2)(x-3)=0 \Rightarrow x=2$ অথবা $x=3$।
              সাধারণ সমাধান: $a_n = A \cdot 2^n + B \cdot 3^n$। $a_0=1$: $A+B=1$। $a_1=4$: $2A+3B=4$। প্রথম সমীকরণ
              থেকে $A=1-B$, বসিয়ে: $2(1-B)+3B=4 \Rightarrow 2+B=4 \Rightarrow B=2$, তাই $A=-1$। বদ্ধ-রূপ:
              $a_n = -2^n + 2 \cdot 3^n$। যাচাই: $a_1 = -2+6=4$ ✓।
            
    
          
    
        
    
      
    2. 
      
  2. 
        কোড প্রসারিত করুন: উপরের কোড সেলে অনুশীলন ১-এর রিকারেন্স ও বদ্ধ-রূপ যোগ করে $n=0$ থেকে $10$ পর্যন্ত দুই পদ্ধতির ফলাফল মিলিয়ে দেখুন।
        
    
          
          
    
            
    
              সম্ভাব্য সমাধান:
            
    
            
    def recurrence2(n):
    a = [1, 4]
    for i in range(2, n + 1):
        a.append(5 * a[i - 1] - 6 * a[i - 2])
    return a[:n + 1]

def closed2(n):
    return -2**n + 2 * 3**n

for n in range(11):
    assert recurrence2(n)[-1] == closed2(n)
print("যাচাই সম্পন্ন")
    
            
    যদি কোনো $n$-এ অমিল দেখেন, প্রথমে $A, B$-এর সাইন (ধনাত্মক/ঋণাত্মক) আবার চেক করুন — এটিই সবচেয়ে সাধারণ ভুল।
    
          
    
        
    
      
    3. 
    

  


  

    
 আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

    
  







  
  
     এই পাঠে ভুল পেয়েছেন? জানান
  





  
    
 আগের পাঠ

    
রিকারেন্স রিলেশন — সংজ্ঞা ও উদাহরণ