Non-homogeneous recurrence আর particular solution

১ · বাড়তি পদওয়ালা recurrence — non-homogeneous কাকে বলে

পর্ব ৪৪ “Recurrence দিয়ে মডেল — Fibonacci, Hanoi আর bit string”-এ আপনি দেখেছেন, অনেক গণনার প্রশ্ন স্বাভাবিকভাবে একটি recurrence হয়ে আসে। পর্ব ৪৫ “Linear recurrence সমাধান — characteristic equation”-এ শিখেছেন a_n = a_n−1 + 2a_n−2 ধরনের recurrence সমাধানের পদ্ধতি: rⁿ বসিয়ে মূল খোঁজা। কিন্তু বাস্তবের বহু recurrence-এ একটি বাড়তি পদ থাকে, যা আগের পদগুলোর ওপর নির্ভর করে না।

“Linear” মানে a-এর পদগুলো শুধু ধ্রুবক দিয়ে গুণ হয়ে যোগ হয়: a_n−1² বা a_n−1a_n−2 নেই। F(n) কিন্তু n-এর যেকোনো ফাংশন হতে পারে, যেমন 1, n², 2ⁿ বা n · 3ⁿ. কয়েকটি উদাহরণ:

প্রথম প্রশ্ন: সমাধান আদৌ একটিই কি না। পর্ব ৪৪-এ strong induction (পর্ব ১১ “Strong induction আর well-ordering”) দিয়ে দেখানো হয়েছে, degree k-এর recurrence-এ k-টি পরপর initial condition দিলে পুরো ধারাটি একটিই, কারণ প্রতিটি নতুন পদ আগের k-টি দিয়ে পুরোপুরি ঠিক হয়। বাড়তি F(n) এই যুক্তিতে কিছুই বদলায় না: সেটিও একটি জানা সংখ্যা। তাই প্রশ্নটি অস্তিত্বের নয়, সূত্র খোঁজার: n = 1000-এর মান লুপ না চালিয়ে কীভাবে লিখব? সেই সূত্রই closed form.

পর্ব ৪৪-এ closed form পাওয়ার একটি পথ দেখেছেন: unrolling, অর্থাৎ পেছনে গুনে যাওয়া। Hanoi-তে H(n) = 2H(n − 1) + 1 = 4H(n − 2) + 2 + 1 = … = 2ⁿH(0) + (2ⁿ⁻¹ + … + 2 + 1), আর শেষের অংশটি একটি geometric series, যোগফল 2ⁿ − 1. পথটি সুন্দর, কিন্তু প্রতিবার একটি নতুন যোগফল চেনার ওপর নির্ভর করে, আর degree 2 বা তার বেশি হলে দ্রুত জট পাকায়। এই পর্বের পদ্ধতি যান্ত্রিক: একই কয়েকটি ধাপ, যেকোনো degree-তে। দুটি পথ একে অপরকে যাচাইও করে।

২ · মূল উপপাদ্য — সব সমাধান = particular + homogeneous

পুরো পদ্ধতি একটি সরল পর্যবেক্ষণের ওপর দাঁড়িয়ে: একই non-homogeneous recurrence-এর দুটি সমাধান বিয়োগ করলে F(n) কাটা যায়। ধরুন কোনোভাবে একটি সমাধান হাতে পেলেন, যেটি initial condition মানে না, শুধু recurrence মানে। একে বলে particular solution. তাহলে বাকি সব সমাধান তার থেকে একটি homogeneous সমাধান দূরে।

1. (a_n) যেকোনো সমাধান ধরুন, আর h_n = a_n − p_n সংজ্ঞায়িত করুন। — সংজ্ঞা
2. দুটি সমীকরণ লিখুন: a_n = ∑_i c_ia_n−i + F(n) আর p_n = ∑_i c_ip_n−i + F(n). প্রথমটি থেকে দ্বিতীয়টি বিয়োগ করলে h_n = ∑_i c_ih_n−i, কারণ F(n) − F(n) = 0. — বিয়োগ, linearity
3. অর্থাৎ (h_n) homogeneous recurrence মানে, আর a_n = p_n + h_n. — ধাপ ১, ২
4. উল্টো দিক: h homogeneous সমাধান হলে p_n + h_n = ∑_i c_i(p_n−i + h_n−i) + F(n), দুটি সমীকরণ যোগ করে। ∎ — যোগ

পর্ব ৪৫-এর ফলের সঙ্গে মেলালে একটি সম্পূর্ণ রেসিপি পাওয়া যায়। Homogeneous অংশের সাধারণ সমাধান k-টি স্বাধীন ধ্রুবক নিয়ে আসে, যেমন আলাদা মূল r₁, …, r_k হলে α₁r₁ⁿ + … + α_kr_kⁿ. তাই মূল recurrence-এর general solution হলো p_n + α₁r₁ⁿ + … + α_kr_kⁿ, আর k-টি initial condition দিয়ে α-গুলো ঠিক হয়। Initial condition বসানোর সময় একটি অনিবার্য ক্রম আছে, যা নিচের ছবিতে দেখুন: আগে p যোগ, তারপর ধ্রুবক খোঁজা।

একটি তুলনা মনে রাখুন। দুটি জমা হিসাবের একই নিয়ম (একই মুনাফা, একই মাসিক জমা), কিন্তু শুরুর জমা আলাদা। তাদের পার্থক্য প্রতি মাসে শুধু ১% হারে বাড়ে, কারণ মাসিক জমা দুই হিসাবেই সমান আর বিয়োগে কাটা যায়। পার্থক্যটি তাই homogeneous ধারা s_n = 1.01 · s_n−1 মানে। উপপাদ্য ২.১ ঠিক এই কথাটিই সাধারণভাবে বলে।

৩ · Undetermined coefficients — F(n) যখন polynomial

এখন বাকি থাকে একটি particular solution খোঁজা। কৌশলটির নাম method of undetermined coefficients: F(n)-এর আকার দেখে একই আকারের একটি “trial” অনুমান করুন, অজানা coefficient রেখে। তারপর recurrence-এ বসিয়ে দুই পাশের n-এর একই ঘাতের coefficient মেলান। F(n) = 2n একটি degree 1-এর polynomial, তাই trial p_n = cn + d. দুটি অজানা, দুটি সমীকরণ।

1homogeneous: r = 32trial pₙ = cn + d3বসানো আর সাজানো4c = −1, d = −3/25α·3ⁿ − n − 3/2; a₀ = 16a₁, a₂, a₃ মেলানো

Hanoi আবার — এক লাইনে

পর্ব ৪৪-এ Tower of Hanoi-র চালের সংখ্যা H(n) = 2H(n − 1) + 1, H(0) = 0 পাওয়া গিয়েছিল, আর পেছনে গুনে গুনে (unrolling) 2ⁿ − 1 অনুমান করে induction-এ প্রমাণ করা হয়েছিল। এবার অনুমান ছাড়াই: homogeneous মূল 2, F(n) = 1 একটি ধ্রুবক, আর 1 মূল নয়। Trial p_n = A: A = 2A + 1, তাই A = −1. সাধারণ সমাধান α · 2ⁿ − 1, আর H(0) = 0 থেকে α = 1. উত্তর H(n) = 2ⁿ − 1.

Particular solution −1-এর একটি সুন্দর মানে আছে: u_n = H(n) + 1 বসালে u_n = 2u_n−1, একটি নিখাদ homogeneous recurrence. ধ্রুবক F-এর ক্ষেত্রে particular solution মানে ধারার “ভারসাম্য বিন্দু”, যেখান থেকে সরে থাকা অংশটুকু শুধু গুণ হতে থাকে।

∑k² — যখন 1 নিজেই মূল

S_n = 1² + 2² + … + n² লিখলে S_n = S_n−1 + n², S₀ = 0. পর্ব ১৭ “Sequence আর summation — closed form আর বিখ্যাত যোগফল”-এ এর সূত্র telescoping দিয়ে বের হয়েছে; এখানে একই সূত্র recurrence থেকে আসে। Homogeneous অংশ S_n = S_n−1-এর মূল 1, আর F(n) = n² = n² · 1ⁿ-এর s-ও 1. এখানেই প্রথম সংঘাত: সরল trial An² + Bn + C কাজ করে না, কারণ ধ্রুবক C নিজেই homogeneous সমাধান, আর বসালে বাঁ পাশ থেকে ডান পাশ বিয়োগে n²-এর পদ কাটা যায়: An² − A(n − 1)² = 2An − A, যার degree মাত্র 1. সমাধান: trial-কে n দিয়ে গুণ করুন।

1. Trial p_n = n(An² + Bn + C) = An³ + Bn² + Cn. — নিয়ম ৪.১, m = 1
2. p_n − p_n−1 = A(3n² − 3n + 1) + B(2n − 1) + C = 3An² + (2B − 3A)n + (A − B + C). — বিস্তার
3. এটি n²-এর সমান হতে হবে: 3A = 1, 2B − 3A = 0, A − B + C = 0. তাই A = 1/3, B = 1/2, C = 1/6. — coefficient মেলানো
4. p_n = n³/3 + n²/2 + n/6 = n(n + 1)(2n + 1)/6, আর p₀ = 0 = S₀, তাই homogeneous অংশের ধ্রুবক 0. S_n = n(n + 1)(2n + 1)/6. ∎ — উপপাদ্য ২.১

যাচাই: S₁₀ = 10 · 11 · 21/6 = 385, আর S₂₀ = 2870; দুটিই পর্ব ১৭-এর মানের সঙ্গে মেলে, আর §৫-এর Python ব্লকেও আসে।

আরেকটি: n রেখায় সমতলের অঞ্চল

পর্ব ৪৪-এর আরেকটি মডেল: সমতলে n-টি রেখা, কোনো দুটি সমান্তরাল নয় আর কোনো তিনটি এক বিন্দুতে মেলে না। n-তম রেখা আগের n − 1টিকে n − 1টি আলাদা বিন্দুতে কাটে, তাই নিজে n-টি টুকরো হয়, আর প্রতিটি টুকরো একটি পুরোনো অঞ্চলকে দুই ভাগ করে। ফলে R(n) = R(n − 1) + n, R(0) = 1. মূল 1, আর F(n) = n · 1ⁿ: আবার সংঘাত, m = 1. Trial n(An + B): n(An + B) − (n − 1)(A(n − 1) + B) = 2An − A + B = n, তাই A = B = 1/2, আর p_n = n(n + 1)/2. R(0) = 1 থেকে ধ্রুবক 1: R(n) = 1 + n(n + 1)/2. যাচাই: 2, 4, 7, 11, recurrence-এর সঙ্গে এক। বাজারঘরের ডেলিভারি-ম্যাপে n-টি সোজা রাস্তা শহরকে সর্বোচ্চ এতগুলো এলাকায় ভাগ করতে পারে।

৪ · Exponential F(n) আর সংঘাতের নিয়ম — কেন n^m দিয়ে গুণ

F(n) = 2ⁿ হলে স্বাভাবিক trial A · 2ⁿ. বেশিরভাগ ক্ষেত্রে তা কাজ করে। কিন্তু homogeneous অংশের মূলও যদি 2 হয়, তাহলে A · 2ⁿ নিজেই homogeneous সমাধান: বসালে বাঁ আর ডান পাশের A-এর পদ হুবহু কাটা যায়, আর পড়ে থাকে 0 = 2ⁿ-এর মতো অসম্ভব সমীকরণ। নিচের stepper এই colliding (সংঘাতের) ক্ষেত্রটি ধাপে ধাপে দেখায়।

1homogeneous: r = 22trial c·2ⁿ ⇒ 0 = 1 ✗3কারণ: c·2ⁿ নিজেই hₙ4নতুন trial cn·2ⁿ ⇒ c = 15(α + n)2ⁿ; a₀ = 16aₙ = (n + 1)2ⁿ ✓

এই উদাহরণটি algorithm বিশ্লেষণে বারবার আসে। Merge sort-এর recurrence T(n) = 2T(n/2) + n-এ n = 2^k আর t_k = T(2^k) বসালে t_k = 2t_k−1 + 2^k: ঠিক উপরের recurrence. T(1) = 1 হলে t_k = (k + 1)2^k, অর্থাৎ T(n) = n(log₂ n + 1). Merge sort-এর বিখ্যাত log n গুণকটি আসলে এই সংঘাতের n-গুণকই! কোড থেকে এমন recurrence লেখা আর সংখ্যায় যাচাইয়ের অভ্যাস DSA কোর্সের পর্ব ০৮-এ আছে; এখানে আমরা দেখলাম log n কেন আসে, তার গাণিতিক কারণ। সাধারণ divide-and-conquer recurrence আর master theorem-এর প্রমাণ পর্ব ৪৭ “Divide-and-conquer recurrence আর master theorem-এর গণিত”-এ আসবে।

ঋণাত্মক s-ও চলে। নিয়মটিতে s যেকোনো অশূন্য ধ্রুবক, তাই F(n) = (−1)ⁿ-এর মতো পর্যায়ক্রমে চিহ্ন-বদলানো পদও একই ছকে পড়ে। যেমন a_n = a_n−1 + 2a_n−2 + (−1)ⁿ: মূল 2 আর −1, আর s = −1 একগুণ মূল, তাই trial An(−1)ⁿ. বসিয়ে (−1)ⁿ দিয়ে ভাগ করলে An = −A(n − 1) + 2A(n − 2) + 1 = An − 3A + 1, তাই A = 1/3 আর p_n = n(−1)ⁿ/3 (scratch-এ ৩০টি পদে মেলানো)। এক সপ্তাহ বেশি, পরের সপ্তাহ কম, এমন দোলানো চাহিদার মডেলে এই ধরনের পদ আসে।

m কীভাবে বের করবেন। χ(x) হলো characteristic polynomial (নিচের রূপরেখায় সংজ্ঞা)। s মূল কি না দেখতে χ(s) হিসাব করুন। শূন্য হলে অন্তত একগুণ মূল; তারপর অন্তরজ χ′(s)-ও শূন্য হলে অন্তত দ্বিগুণ, আর এভাবে চলতে থাকে। যেমন χ(x) = x² − 4x + 4-এ χ(2) = 0 আর χ′(x) = 2x − 4, χ′(2) = 0, কিন্তু χ″(2) = 2 ≠ 0: তাই m = 2. পরীক্ষায় সাধারণত মূলগুলো সরাসরি factor করে দেখাই সহজ, কিন্তু বড় degree-তে এই পরীক্ষা কাজে লাগে।

প্রমাণের রূপরেখা। পর্ব ৪৫-এ degree k-এর সাধারণ ফলটি (পুনরাবৃত্ত মূল r-এর জন্য rⁿ, nrⁿ, …, n^m−1rⁿ) বলা হয়েছে; এখানে সেটি ব্যবহার করি। একটি ধারার ওপর “এক ধাপ সামনে সরাও” কাজটিকে E লিখুন: (Ea)_n = a_n+1.

1. Recurrence-টিকে এক জায়গায় আনলে লেখা যায় χ(E)a = G, যেখানে χ(x) = x^k − c₁x^k−1 − … − c_k হলো characteristic polynomial আর G_n = F(n + k). — সূচক সরানো
2. q একটি degree j-এর polynomial হলে (E − s) প্রয়োগে q(n)sⁿ হয় s(q(n + 1) − q(n))sⁿ, যার polynomial অংশের degree j − 1. তাই (E − s)^t+1 প্রয়োগে G পুরো মুছে যায়। এই (E − s)^t+1-কে G-এর annihilator বলে। — পার্থক্যে degree কমে
3. অতএব প্রতিটি সমাধান a একটি বড় homogeneous recurrence মানে: (E − s)^t+1χ(E)a = 0, যার characteristic polynomial χ(x)(x − s)^t+1. এতে s-এর গুণিতা m + t + 1. — E-এর polynomial গুণ বিনিময়যোগ্য
4. পর্ব ৪৫-এর উপপাদ্য অনুযায়ী a = (χ-এর মূল থেকে আসা পদ) + n^m(A₀ + … + A_tn^t)sⁿ; sⁿ, …, n^m−1sⁿ-এর পদগুলো আগেই χ-এর অংশ, তাই প্রথম ভাগে ঢুকে যায়। — পুনরাবৃত্ত মূলের উপপাদ্য
5. প্রথম ভাগ নিজে homogeneous সমাধান, তাই উপপাদ্য ২.১ অনুযায়ী তা বাদ দিলে যা থাকে, n^m(A₀ + … + A_tn^t)sⁿ, সেটিও একটি সমাধান: এটিই চাওয়া particular solution. ∎ — উপপাদ্য ২.১

রূপরেখাটি দেখায় trial form-টি “আন্দাজ” নয়: সমাধানের আকার প্রমাণিতভাবে এটিই, আমরা শুধু coefficient-গুলো জানি না। পুরো বিস্তারিত (A-গুলো সত্যিই একটিমাত্র রৈখিক system-এর সমাধান) generating function দিয়ে আরও পরিষ্কার হয়, যা পর্ব ৪৮ “Generating function — গণনাকে বীজগণিতে রূপান্তর”-এ আসবে।

শেষ সারির নিয়মটির নাম superposition principle: p⁽¹⁾ যদি F₁-এর আর p⁽²⁾ যদি F₂-এর particular solution হয়, তাহলে p⁽¹⁾ + p⁽²⁾ হলো F₁ + F₂-এর particular solution; দুটি সমীকরণ যোগ করলেই প্রমাণ। একটি সতর্কতা: F(n) = n² হলেও trial-এ নিচের সব ঘাত রাখতে হয় (An² + Bn + C), কারণ বসানোর পর নিচের ঘাতগুলো আপনাআপনি তৈরি হয়। আর F(n) যদি এই ছকে না পড়ে, যেমন n! বা 1/n, তাহলে এই পদ্ধতি খাটে না; তখন §৭-এর summation factor বা generating function লাগে।

Superposition-এর একটি উদাহরণ। a_n = 2a_n−1 + n + 3ⁿ, a₀ = 1. মূল 2; বাড়তি পদের দুই অংশের কোনোটিই সংঘাত করে না (s = 1 আর s = 3). প্রথম অংশ n-এর জন্য trial An + B: An + B = 2A(n − 1) + 2B + n থেকে A = −1, B = −2. দ্বিতীয় অংশ 3ⁿ-এর জন্য trial C · 3ⁿ: 3C = 2C + 3, তাই C = 3. যোগ করে a_n = α · 2ⁿ − n − 2 + 3ⁿ⁺¹; a₀ = 1 থেকে α − 2 + 3 = 1, তাই α = 0. উত্তর a_n = 3ⁿ⁺¹ − n − 2: ধারা 1, 6, 23, 76, 237, recurrence থেকেও হুবহু তাই (scratch-এ ১২টি পদ মেলানো)। এখানে α = 0 হওয়া কাকতাল মাত্র; সাধারণত তা হয় না।

৫ · Python-এ একটি সাধারণ first-order সমাধানকারী

নিয়ম ৪.১-কে এবার কোডে বসাই। নিচের ফাংশন a_n = c · a_n−1 + p(n) · sⁿ ধরনের যেকোনো recurrence নেয়, যেখানে p একটি polynomial (coefficient-এর তালিকা হিসেবে দেওয়া)। এটি নিজেই সংঘাত চেনে (s = c হলে m = 1), trial বসিয়ে coefficient-এর রৈখিক system বানায়, Fraction দিয়ে Gauss–Jordan পদ্ধতিতে সমাধান করে, আর সবশেষে initial condition থেকে α বের করে। তারপর ৪০টি পদ সরাসরি recurrence চালিয়ে closed form-এর সঙ্গে মেলায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from fractions import Fraction as Fr

def solve(c, poly, s, a0):            # a_n = c a_(n-1) + poly(n) s^n
    t, m = len(poly) - 1, int(s == c)  # m = 1 when s collides with c
    def trial(q, n):                  # n^m (q0 + q1 n + ...) s^n
        return n**m * sum(x * n**i for i, x in enumerate(q)) * Fr(s)**n
    def F(n):
        return sum(b * n**i for i, b in enumerate(poly)) * Fr(s)**n
    unit = [[int(i == j) for i in range(t + 1)] for j in range(t + 1)]
    A = [[trial(u, n) - c * trial(u, n - 1) for u in unit] + [F(n)]
         for n in range(1, t + 2)]    # trial must satisfy the recurrence
    for i in range(t + 1):            # Gauss-Jordan with Fractions
        k = next(r for r in range(i, t + 1) if A[r][i] != 0)
        A[i], A[k] = A[k], A[i]
        A[i] = [x / A[i][i] for x in A[i]]
        for r in range(t + 1):
            if r != i:
                A[r] = [x - A[r][i] * y for x, y in zip(A[r], A[i])]
    q = [row[-1] for row in A]
    alpha = a0 - trial(q, 0)          # fit the initial value last
    return (lambda n: alpha * Fr(c)**n + trial(q, n)), q, m

cases = [("3a+2n", 3, [0, 2], 1, 1), ("2a+2^n", 2, [1], 2, 1),
         ("a+n^2", 1, [0, 0, 1], 1, 0), ("2a+1", 2, [1], 1, 0),
         ("2a+n2^n", 2, [0, 1], 2, 1)]
for name, c, poly, s, a0 in cases:
    f, q, m = solve(c, poly, s, a0)
    a, ok = Fr(a0), True
    for n in range(1, 41):            # iterate the recurrence itself
        a = c * a + sum(b * n**i for i, b in enumerate(poly)) * s**n
        ok = ok and a == f(n)
    print(f"{name:8} m={m} q={[str(x) for x in q]} a_10={f(10)} ok={ok}")

3a+2n    m=0 q=['-3/2', '-1'] a_10=147611 ok=True
2a+2^n   m=1 q=['1'] a_10=11264 ok=True
a+n^2    m=1 q=['1/6', '1/2', '1/3'] a_10=385 ok=True
2a+1     m=0 q=['-1'] a_10=1023 ok=True
2a+n2^n  m=1 q=['1/2', '1/2'] a_10=57344 ok=True

৬ · ঋণ পরিশোধ — মাসিক কিস্তির closed form

পর্ব ৪৪-এ বাজারঘরের একটি কাল্পনিক ব্যবসায়িক ঋণের মডেল বানানো হয়েছিল। ধরুন ঋণ L টাকা, মাসিক সুদের হার r (যেমন r = 0.01, অর্থাৎ মাসে ১%; এটি শুধু উদাহরণের সংখ্যা, কোনো আসল ব্যাংকের হার নয়), আর প্রতি মাসের শেষে একই কিস্তি P দেওয়া হয়। n মাস পরে বাকি b_n হলে

b_n = (1 + r) · b_n−1 − P, b₀ = L

এটি এক ধরনের compound interest: সুদ বাকির ওপর বসে, আর বাকিতে আগের সুদও আছে। প্রশ্ন: N মাসে পুরো ঋণ শোধ করতে P কত হবে? লুপ চালিয়ে চেষ্টা-ভুল করা যায়, কিন্তু closed form সরাসরি উত্তর দেয়। এই হিসাবের নাম loan amortization.

1. Homogeneous অংশ b_n = (1 + r)b_n−1-এর মূল 1 + r, তাই h_n = α(1 + r)ⁿ. — পর্ব ৪৫
2. F(n) = −P একটি ধ্রুবক (s = 1), আর r > 0 বলে 1 ≠ 1 + r: সংঘাত নেই। Trial p_n = A: A = (1 + r)A − P, তাই A = P/r. — নিয়ম ৪.১
3. উপপাদ্য ২.১: b_n = α(1 + r)ⁿ + P/r; n = 0-তে α = L − P/r. — initial condition সবশেষে
4. b_N = 0 মানে (L − P/r)(1 + r)^N = −P/r. দুই পাশ r দিয়ে গুণ করে সাজালে P((1 + r)^N − 1) = Lr(1 + r)^N; (1 + r)^N > 1, তাই ভাগ বৈধ। ∎ — বীজগণিত

কিস্তির কতটা মূল ঋণে যায়? n-তম কিস্তিতে সুদ r · b_n−1, আর বাকিটুকু মূল ঋণ কমায়: b_n−1 − b_n. Closed form থেকে b_n−1 − b_n = −(L − P/r)(1 + r)ⁿ⁻¹ · r = (P − rL)(1 + r)ⁿ⁻¹. অর্থাৎ মূল ঋণে যাওয়া অংশ প্রতি মাসে (1 + r) গুণ বাড়ে, আর সুদের অংশ সেই হারেই কমে, কারণ দুটির যোগফল সবসময় P. প্রথম মাসে এটি P − rL, যা নিচের ব্লকের উদাহরণে প্রায় ৯,৪৬২ টাকা।

একই সূত্র, অন্য দিক থেকে। কিস্তির সূত্রটি উল্টে লিখলে L = P(1 − (1 + r)^−N)/r = P/(1 + r) + P/(1 + r)² + … + P/(1 + r)^N, একটি সসীম geometric series (পর্ব ১৭)। মানেটি সুন্দর: k মাস পরের P টাকার “আজকের মূল্য” P/(1 + r)^k, কারণ আজ সেই পরিমাণ রাখলে k মাসে সুদে-আসলে P হতো। ঋণদাতা আজ যে L দেন, তা ঠিক ভবিষ্যতের সব কিস্তির আজকের মূল্যের যোগফল। Recurrence-এর পথ আর এই যোগফলের পথ একই উত্তরে পৌঁছায়, যা দুটি স্বাধীন যাচাইয়ের কাজ করে।

P/r সংখ্যাটির একটি পরিষ্কার মানে আছে: বাকি ঠিক P/r হলে মাসের সুদ r · P/r = P, কিস্তির সমান, তাই বাকি কখনো বদলায় না। এটিই ভারসাম্য বিন্দু (Hanoi-র −1-এর মতো)। L < P/r হলে ভারসাম্য থেকে দূরত্ব L − P/r ঋণাত্মক, আর তা প্রতি মাসে (1 + r) গুণ বাড়তে বাড়তে বাকিকে শূন্যে নামায়। P ≤ Lr হলে কিস্তি সুদও ঢাকে না, আর ঋণ কখনো শোধ হয় না।

উদাহরণ: L = 1,20,000 টাকা, r = 1/100, N = 12. নিচের ব্লক কিস্তি নির্ভুলভাবে বের করে, প্রতি মাসের খাতা (ledger) closed form-এর সঙ্গে মেলায়, আর দেখায় পয়সায় গোল করলে কী হয়। এটি শুধু গণিতের উদাহরণ, কোনো আর্থিক পরামর্শ নয়; বাস্তব ঋণে ফি, সুদ হিসাবের নিয়ম আর দিন গোনার রীতি আলাদা হতে পারে।

from fractions import Fraction as Fr

L, r, N = Fr(120000), Fr(1, 100), 12  # loan, example monthly rate, months
g = (1 + r) ** N
P = L * r * g / (g - 1)               # the payment that makes b_N = 0
print("exact monthly payment P ~", round(float(P), 4))

def closed(n, pay):                   # b_n = (L - pay/r)(1+r)^n + pay/r
    return (L - pay / r) * (1 + r) ** n + pay / r

b = L
for n in range(1, N + 1):             # month-by-month ledger
    b = (1 + r) * b - P
    if n in (1, 2, 6, 12):
        print(f"month {n:2}: ledger {float(b):10.2f}"
              f"   formula {float(closed(n, P)):10.2f}")
print("ledger == formula, and b_12 == 0:", b == closed(N, P) == 0)

P2 = Fr(round(P * 100), 100)          # paid in whole paisa
print("rounded payment", float(P2), "-> left after 12 months:",
      round(float(closed(N, P2)), 4))
print("total paid", float(P2 * N), "  of which interest", float(P2 * N - L))

exact monthly payment P ~ 10661.8546
month  1: ledger  110538.15   formula  110538.15
month  2: ledger  100981.67   formula  100981.67
month  6: ledger   61790.53   formula   61790.53
month 12: ledger       0.00   formula       0.00
ledger == formula, and b_12 == 0: True
rounded payment 10661.85 -> left after 12 months: 0.0589
total paid 127942.2   of which interest 7942.2

উল্টো দিক: সঞ্চয়ের লক্ষ্য

§১-এর সঞ্চয় হিসাবেও একই পদ্ধতি। s_n = 1.01 · s_n−1 + 5000, s₀ = 0. মূল 1.01, trial A: A = 1.01A + 5000, তাই A = −5,00,000. s_n = α(1.01)ⁿ − 500000, আর s₀ = 0 থেকে α = 500000: s_n = 500000((1.01)ⁿ − 1). এক বছরে s₁₂ ≈ ৬৩,৪১২.৫২ টাকা, যার ৬০,০০০ নিজের জমা আর বাকিটা মুনাফা। প্রশ্ন: কত মাসে জমা ১,০০,০০০ টাকা ছাড়াবে? Closed form থাকায় লুপ লাগে না: (1.01)ⁿ ≥ 1.2, অর্থাৎ n ≥ ln 1.2/ln 1.01 ≈ 18.3, তাই ১৯ মাস (scratch-এ লুপ চালিয়েও ১৯)। Particular solution এখানে ঋণাত্মক, −5,00,000: গণিতের দিক থেকে এটি সেই “ভারসাম্য বিন্দু”, যেখানে থাকলে মুনাফার বিয়োগ আর জমা পরস্পর কাটত; বাস্তবে এর কোনো মানে নেই, তবু সূত্রে এটি অপরিহার্য।

৭ · চলমান coefficient আর summation factor — quicksort-এর recurrence

এতক্ষণ coefficient c ছিল ধ্রুবক। কিন্তু algorithm-এর বিশ্লেষণে প্রায়ই আসে a_n = g_n · a_n−1 + h_n, যেখানে g_n নিজেই n-এর ফাংশন, যেমন (n + 1)/n. তখন characteristic equation কাজ করে না, কারণ rⁿ বসালে n বাদ যায় না। এর জন্য একটি পুরোনো, সরল কৌশল আছে।

1. Recurrence-কে G_n দিয়ে ভাগ করুন: a_n/G_n = g_na_n−1/G_n + h_n/G_n = a_n−1/G_n−1 + h_n/G_n, কারণ G_n = g_nG_n−1. — G_n ≠ 0
2. u_n = a_n/G_n ধরলে u_n − u_n−1 = h_n/G_n. — নতুন চলক
3. k = 1 থেকে n পর্যন্ত যোগ করলে বাঁ পাশ কাটাকাটি হয়ে u_n − u₀ থাকে (telescoping sum, পর্ব ১৭)। u₀ = a₀, তাই G_n দিয়ে গুণ করলে সূত্রটি আসে। ∎ — telescoping

1/G_n-কে বলে summation factor: এই গুণকে গুণ করলে recurrence একটি সাধারণ যোগফলে পরিণত হয়। ধ্রুবক g_n = c-এ G_n = cⁿ, আর সূত্রটি §৫-এর মতোই ফল দেয়, তবে যোগফলটি নিজে বের করতে হয়।

ছোট উদাহরণ। a_n = n · a_n−1 + n!, a₀ = 1. এখানে F(n) = n! কোনো trial-এর ছকে পড়ে না, আর coefficient n-ও চলমান। g_n = n, তাই G_n = n!, আর h_k/G_k = k!/k! = 1. সূত্র থেকে a_n = n!(1 + n) = (n + 1)!. যাচাই: a₁ = 1 + 1 = 2, a₂ = 4 + 2 = 6, a₃ = 18 + 6 = 24, ঠিক 2!, 3!, 4!.

Quicksort-এর গড় তুলনা

পর্ব ৪০ “Random variable আর প্রত্যাশা — linearity-র জাদু”-এ randomized quicksort-এর প্রত্যাশিত তুলনা 2(n + 1)H_n − 4n দেখানো হয়েছিল indicator আর linearity দিয়ে, যেখানে harmonic number H_n = 1 + 1/2 + … + 1/n. এবার একই উত্তর recurrence থেকে আসে। n-টি আলাদা key-এ pivot সমান সম্ভাবনায় k-তম ছোট (k = 1, …, n). Pivot-এর সঙ্গে বাকি n − 1টির তুলনা হয়, তারপর k − 1 আর n − k আকারের দুটি অংশ। শর্তসাপেক্ষ প্রত্যাশার গড় (total expectation) নিলে, C(n) = প্রত্যাশিত তুলনা হলে

C(n) = n − 1 + (1/n)∑_k=1ⁿ (C(k − 1) + C(n − k)) = n − 1 + (2/n)∑_j=0ⁿ⁻¹ C(j), C(0) = 0

যুক্তিটি ধাপে ধাপে: (১) pivot-এর rank k হওয়ার সম্ভাবনা 1/n, প্রতিটি k-এর জন্য; (২) rank k ধরে নিলে বাকি কাজ দুটি স্বাধীন ছোট সমস্যা, আর ছোট অংশের ভেতরের ক্রমও এলোমেলো থাকে, তাই তাদের প্রত্যাশিত তুলনা C(k − 1) আর C(n − k); (৩) total expectation-এর নিয়মে (পর্ব ৪০-এর linearity আর পর্ব ৩৯-এর শর্তসাপেক্ষ ভাগ মিলিয়ে) মোট প্রত্যাশা = প্রতিটি k-এর শর্তসাপেক্ষ প্রত্যাশার গড়। দুটি যোগফল একই পদগুলো উল্টো ক্রমে গোনে, তাই 2 গুণ। এখানে C(n) আগের সব পদের ওপর নির্ভর করে: এমন recurrence-কে বলে full-history recurrence. প্রথম কাজ একে first-order বানানো।

1C(n) = n−1 + (2/n)∑C(j)2n দিয়ে গুণ3n−1-এর রূপ বিয়োগ4n(n+1) দিয়ে ভাগ5telescoping যোগ6C(n) = 2(n+1)Hₙ − 4n

নিচের ব্লক তিনটি জিনিস মেলায়: (১) recurrence-টি নিজে ঠিক কি না, সব n! ইনপুট-ক্রমে প্রথম উপাদানকে pivot ধরে গড় তুলনা গুনে (এলোমেলো ইনপুটে প্রথম উপাদান pivot আর যেকোনো ইনপুটে এলোমেলো pivot, দুটির বণ্টন একই); (২) recurrence আর closed form n ≤ 30-এ হুবহু এক কি না; (৩) stepper-এর ধাপ ৩-এর first-order রূপটি।

from fractions import Fraction as Fr
from itertools import permutations

def comparisons(lst):                 # quicksort, first element as pivot
    if len(lst) <= 1:
        return 0
    p = lst[0]
    small = [x for x in lst[1:] if x < p]
    big = [x for x in lst[1:] if x > p]
    return len(lst) - 1 + comparisons(small) + comparisons(big)

C = [Fr(0)]                           # C(n) = n-1 + (2/n)(C(0)+...+C(n-1))
for n in range(1, 31):
    C.append(n - 1 + Fr(2, n) * sum(C))
H = [Fr(0)]
for k in range(1, 31):
    H.append(H[-1] + Fr(1, k))
closed = [2 * (n + 1) * H[n] - 4 * n for n in range(31)]

for n in range(1, 7):                 # average over all n! input orders
    perms = list(permutations(range(n)))
    avg = Fr(sum(comparisons(list(p)) for p in perms), len(perms))
    print(f"n = {n}: brute force {str(avg):>6}   recurrence {str(C[n]):>6}")
print("recurrence == 2(n+1)H_n - 4n for all n <= 30:", C == closed)
ok = all(n * C[n] == (n + 1) * C[n - 1] + 2 * (n - 1) for n in range(1, 31))
print("n C(n) == (n+1) C(n-1) + 2(n-1) for all n <= 30:", ok)
print("C(30) ~", round(float(C[30]), 3), "  C(10) ~", round(float(C[10]), 3))

n = 1: brute force      0   recurrence      0
n = 2: brute force      1   recurrence      1
n = 3: brute force    8/3   recurrence    8/3
n = 4: brute force   29/6   recurrence   29/6
n = 5: brute force   37/5   recurrence   37/5
n = 6: brute force 103/10   recurrence 103/10
recurrence == 2(n+1)H_n - 4n for all n <= 30: True
n C(n) == (n+1) C(n-1) + 2(n-1) for all n <= 30: True
C(30) ~ 127.689   C(10) ~ 24.437

একই recurrence আরেকটি প্রশ্নের উত্তরও দেয়। এলোমেলো ক্রমে n-টি আলাদা key একটি binary search tree-তে ঢোকালে প্রথম key-টি root হয়, আর সেটি সমান সম্ভাবনায় যেকোনো rank-এর; বাঁ আর ডান subtree আবার এলোমেলো ক্রমের ছোট গাছ। প্রতিটি key ঢোকানোর সময় যতগুলো তুলনা হয়, তার মোট যোগফল ঠিক quicksort-এর তুলনার মতো একই recurrence মানে, কারণ root-এর সঙ্গে বাকি n − 1টির তুলনা হয়, তারপর দুই ভাগ। তাই এলোমেলো BST বানাতে গড়ে 2(n + 1)H_n − 4n তুলনা, আর একটি key-এর গড় গভীরতা প্রায় 2 ln n. এক recurrence, দুটি algorithm: গণিতের এই পুনর্ব্যবহারই recurrence শেখার বড় লাভ।

৮ · পরীক্ষার অঙ্ক আর সাধারণ ভুল

অঙ্ক ১: দ্বিতীয় ক্রম, সংঘাত ছাড়া

a_n = 5a_n−1 − 6a_n−2 + 7ⁿ, a₀ = a₁ = 0. সমাধান করুন।

1. Characteristic equation r² − 5r + 6 = 0, মূল 2 আর 3. h_n = α2ⁿ + β3ⁿ.
2. s = 7 মূল নয়: trial A · 7ⁿ. বসিয়ে 7ⁿ⁻² দিয়ে ভাগ: 49A = 35A − 6A + 49, তাই 20A = 49, A = 49/20.
3. a_n = α2ⁿ + β3ⁿ + (49/20)7ⁿ. a₀ = 0: α + β = −49/20. a₁ = 0: 2α + 3β = −343/20. সমাধানে α = 49/5, β = −49/4.
4. উত্তর: a_n = (49/20)(7ⁿ − 5 · 3ⁿ + 4 · 2ⁿ). যাচাই: a₂ = (49/20)(49 − 45 + 16) = 49 = 5 · 0 − 6 · 0 + 49 ✓, আর a₃ = 588 (scratch-এ মেলানো)।

অঙ্ক ২: polynomial × exponential, সংঘাতসহ

a_n = 2a_n−1 + n · 2ⁿ, a₀ = 1.

1. মূল 2, আর s = 2: m = 1. F-এর polynomial অংশ n, degree 1, তাই trial n(An + B)2ⁿ.
2. বসিয়ে 2ⁿ দিয়ে ভাগ: An² + Bn = A(n − 1)² + B(n − 1) + n, অর্থাৎ 0 = (1 − 2A)n + (A − B). তাই A = B = 1/2.
3. a_n = α2ⁿ + n(n + 1)2ⁿ⁻¹; a₀ = 1 থেকে α = 1. উত্তর: a_n = 2ⁿ⁻¹(n² + n + 2). যাচাই: 1, 4, 16, 56, 176, recurrence-এর মানের সঙ্গে এক।

অঙ্ক ৩: ঋণের কিস্তি

৫০,০০০ টাকার একটি কাল্পনিক ঋণ, মাসিক হার ২% (উদাহরণমাত্র), ৬ মাসে সমান কিস্তিতে শোধ। মাসিক কিস্তি আর মোট সুদ কত?

1. উপপাদ্য ৬.১: P = 50000 · 0.02 · (1.02)⁶/((1.02)⁶ − 1). (1.02)⁶ ≈ 1.126162.
2. P ≈ 1000 × 1.126162/0.126162 ≈ ৮,৯২৬.২৯ টাকা।
3. মোট পরিশোধ ≈ 6 × 8926.29 ≈ ৫৩,৫৫৭.৭৪, তাই মোট সুদ প্রায় ৩,৫৫৭.৭৪ টাকা (scratch-এ Fraction দিয়ে মেলানো, আর ৬ মাস পরে বাকি ঠিক শূন্য)।

অঙ্ক ৪: শুধু trial form

a_n = 6a_n−1 − 9a_n−2 + F(n)-এ (characteristic equation (r − 3)² = 0, মূল 3 দ্বিগুণ) নিচের প্রতিটি F-এর trial লিখুন।

যুক্তির ভুল ধরুন: “আগে ধ্রুবক, পরে particular”

একজন a_n = 3a_n−1 + 2n, a₀ = 1 এভাবে সমাধান করলেন: “h_n = α · 3ⁿ; a₀ = 1 বসিয়ে α = 1. Particular p_n = −n − 3/2. তাই a_n = 3ⁿ − n − 3/2.”

ভুল কোথায়: initial condition বসানো হয়েছে শুধু homogeneous অংশে। কিন্তু a₀ = 1 শর্তটি আসল ধারার, h-এর নয়। ফলে তাঁর সূত্রে a₀ = 1 − 0 − 3/2 = −1/2, যা 1 নয়, আর a₁ = 3 − 1 − 3/2 = 1/2, যেখানে আসল মান 5. উপপাদ্য ২.১-এর ক্রম মানুন: আগে a_n = α · 3ⁿ + p_n লিখুন, তারপর পুরো যোগফলে a₀ বসান: α = 5/2. একটি সহজ অভ্যাস এই ধরনের ভুল সঙ্গে সঙ্গে ধরে: শেষ সূত্রে n = 0, 1, 2 বসিয়ে recurrence-এর মানের সঙ্গে মেলানো।

৯ · AI-এর যুগে — particular solution যাচাই

AI সহকারী recurrence সমাধানে খুব দ্রুত, আর উত্তরটি দেখতে প্রায় সবসময় পরিপাটি। কিন্তু এই বিষয়ের ভুলগুলো প্রায়ই ছোট একটি সিদ্ধান্তে থাকে: কোন trial, কোন ক্রমে initial condition. সুখবর হলো, এখানে যাচাই সবচেয়ে সহজ: সূত্রে n = 0, 1, 2, 3 বসিয়ে recurrence-এর মানের সঙ্গে মেলালেই হয়। কয়েকটি নিয়মিত ভুল:

একটি নমুনা ভুল। ধরুন একটি সহকারী a_n = 2a_n−1 + 2ⁿ, a₀ = 1-এর উত্তর দিল “a_n = 2ⁿ⁺¹ − 1”, সঙ্গে কয়েক লাইনের আত্মবিশ্বাসী ব্যাখ্যা। দেখতে Hanoi-র মতো, তাই বিশ্বাসযোগ্য মনে হয়। n = 0-তে 2 − 1 = 1, মিলে গেল। কিন্তু n = 1-এ সূত্র দেয় 3, আর recurrence দেয় 2 · 1 + 2 = 4. একটি মাত্র পদ বসিয়েই ভুল ধরা পড়ল। সঠিক উত্তর (n + 1)2ⁿ, সংঘাতের ক্ষেত্র, যা §৪-এর stepper-এ আছে। শিক্ষা: n = 0-এ মেলা যথেষ্ট নয়, কারণ ধ্রুবক ঠিক ওই বিন্দুতেই মেলানো হয়; অন্তত আরও দুটি পদ মেলাতে হয়।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• Characteristic equation-এর মূল নিজে বের করে মিলিয়েছি, গুণিতাসহ
• s মূলের সঙ্গে সংঘাত করে কি না দেখেছি, আর trial-এ n^m আছে কি না
• Trial-এ polynomial-এর সব নিচের ঘাত রাখা হয়েছে কি না দেখেছি
• Initial condition পুরো সমাধানে বসানো হয়েছে, আর n = 0, 1, 2-এ সূত্র মিলেছে
• Fraction দিয়ে অন্তত ৩০টি পদ recurrence আর closed form-এ হুবহু মিলিয়েছি
• উদ্ধৃত উপপাদ্যের শর্ত (ধ্রুবক coefficient, g_n ≠ 0, r > 0) উল্লেখ আছে কি না দেখেছি

আরেকটি ভালো অভ্যাস হলো AI-কে দুটি আলাদা পথে একই উত্তর বের করতে বলা: একবার undetermined coefficients দিয়ে, আরেকবার unrolling বা summation factor দিয়ে। দুই পথের উত্তর মিললে আস্থা বাড়ে; না মিললে অন্তত একটি পথে ভুল আছে, আর ছোট n-এ সংখ্যা বসিয়ে দেখলেই বোঝা যায় কোনটিতে। মনে রাখবেন, AI যদি কোনো পাঠ্যবইয়ের নাম বা পৃষ্ঠা উদ্ধৃত করে, সেটিও নিজে মিলিয়ে দেখতে হবে; বানানো উৎস এই বিষয়েও দেখা যায়।

এই পর্বের প্রতিটি সমাধান তিনটি সিদ্ধান্তে দাঁড়ায়: homogeneous মূল, trial form, আর initial condition-এর ক্রম। AI-এর উত্তর পড়ার সময় এই তিনটিই আলাদা করে প্রশ্ন করুন; বাকিটা সাধারণ বীজগণিত, যা Python এক মুহূর্তে মিলিয়ে দেয়।