জেনারেটিং ফাংশন পরিচিতি

১ · জেনারেটিং ফাংশন কী?

এতক্ষণ আমরা একটি সিকোয়েন্সকে দেখেছি সংখ্যার একটি তালিকা হিসেবে: $a_0, a_1, a_2, \dots$। একটি জেনারেটিং ফাংশনGenerating Functionএকটি সিকোয়েন্স $a_0,a_1,a_2,\dots$-কে একটি একক বীজগাণিতিক বস্তু — একটি ফরমাল পাওয়ার সিরিজ — হিসেবে এনকোড করার কৌশল, যেখানে $a_n$ হলো $x^n$-এর গুণাঙ্ক। "ফরমাল" মানে আমরা $x$-এর কোনো নির্দিষ্ট সাংখ্যিক মান বসাচ্ছি না — এটি শুধু গুণাঙ্কগুলো ধরে রাখার একটি খাতা মাত্র। একই সিকোয়েন্সকে সম্পূর্ণ ভিন্নভাবে দেখে — একটি একক বীজগাণিতিক বস্তু হিসেবে, যেখানে প্রতিটি $a_n$ একটি পাওয়ার সিরিজের $x^n$ পদের গুণাঙ্ক —

$$G(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \dots$$

২ · সবচেয়ে সহজ উদাহরণ — জ্যামিতিক সিকোয়েন্স

ধরুন সিকোয়েন্সটি হলো $a_n = 1$ প্রতিটি $n \geq 0$-এর জন্য — অর্থাৎ $1, 1, 1, 1, \dots$। তাহলে —

$$G(x) = 1 + x + x^2 + x^3 + \dots$$

এটি একটি সুপরিচিত সিরিজ — জ্যামিতিক সিরিজ (Geometric Series)। এর একটি বদ্ধ-রূপ পরিচিতি আছে —

$$G(x) = \frac{1}{1-x}$$

এই অভেদটি সহজেই যাচাই করা যায়: $(1-x)(1+x+x^2+\dots) = 1+x+x^2+\dots - x - x^2 - x^3 - \dots = 1$ (বাকি সব পদ বাতিল হয়ে যায়)। এভাবে একটি অসীম সিকোয়েন্স একটি ছোট্ট বীজগাণিতিক রাশিতে "সংকুচিত" হয়ে যায়।

৩ · জেনারেটিং ফাংশন দিয়ে রিকারেন্স সমাধান — একটি ঝলক

জেনারেটিং ফাংশনের সবচেয়ে শক্তিশালী ব্যবহার হলো রিকারেন্স রিলেশন সমাধান করা — L30-এর ক্যারেক্টারিস্টিক ইকুয়েশন পদ্ধতির একটি বিকল্প বীজগাণিতিক পথ। ধারণাটি (বিস্তারিত ডেরিভেশন ছাড়া) এরকম: রিকারেন্স $a_n = 2a_{n-1}+1$, $a_0=0$-এর জন্য, প্রতিটি পাশকে $x^n$ দিয়ে গুণ করে সব $n \geq 1$-এর উপর যোগ করলে, এবং $G(x)=\sum a_n x^n$ সংজ্ঞা ব্যবহার করে, শেষ পর্যন্ত পাওয়া যায় —

$$G(x) = \frac{x}{(1-x)(1-2x)}$$

এরপর পার্শিয়াল ফ্র্যাকশন ডিকম্পোজিশন (একটি বীজগাণিতিক কৌশল যা এই রাশিকে সহজ ভগ্নাংশের যোগফলে ভাঙে) প্রয়োগ করলে বদ্ধ-রূপ সূত্র পাওয়া যায় —

$$a_n = 2^n - 1$$

# a_n = 2*a_(n-1) + 1, a_0 = 0
# বদ্ধ-রূপ সূত্র: a_n = 2**n - 1 — দুইভাবে যাচাই

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

def closed_form(n):
    return 2**n - 1

N = 10
recursive_values = recurrence(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..10 পর্যন্ত সব মান মিলেছে।")