Linear recurrence সমাধান — characteristic equation

১ · Linear homogeneous recurrence — কোনটি, কোনটি নয়

আগের পর্ব ৪৪ “Recurrence দিয়ে মডেল — Fibonacci, Hanoi আর bit string”-এ নানা গণনার প্রশ্নকে recurrence-এর ভাষায় লেখা হয়েছে: একটি ক্রমের প্রতিটি পদ আগের কয়েকটি পদ দিয়ে লেখা নিয়ম। তখন সমাধান মানে ছিল কয়েকটি পদ খুলে (unrolling) একটি নিয়ম অনুমান করা, তারপর induction দিয়ে প্রমাণ করা (পর্ব ১০ “Mathematical induction — এক ধাপ থেকে অসীম পর্যন্ত”). অনুমান সব সময় চোখে পড়ে না। যেমন 2, 7, 11, 25, 47, 97, … দেখে নিয়মটি অনুমান করা সহজ নয়। এই পর্বে একটি বড় শ্রেণির recurrence-এর জন্য অনুমান ছাড়াই closed form বের করার একটি যান্ত্রিক পদ্ধতি শিখবেন।

এই শ্রেণিটি সংকীর্ণ শোনালেও কম্পিউটার বিজ্ঞানে বারবার আসে। Dynamic programming-এ “শেষ ধাপে কী হলো” ধরে গোনার প্রশ্ন (টাইল বসানো, সিঁড়ি ভাঙার উপায়, নিষিদ্ধ pattern ছাড়া string) প্রায়ই এমন recurrence দেয়। Linear feedback shift register (LFSR) নামের সরল pseudorandom bit উৎপাদক আসলে mod 2-এ একটি linear recurrence, যেমন x_n = x_n−3 ⊕ x_n−4. Digital signal processing-এর অনেক filter-ও একই গঠনের। তাই সমাধানের পদ্ধতিটি একবার শিখলে অনেক জায়গায় কাজে লাগে।

1. অস্তিত্ব: a₀, …, a_k−1 দেওয়া; n ≥ k-এর জন্য recurrence-এর ডান পাশ শুধু আগের পদ দিয়ে a_n গণনা করে। তাই প্রতিটি পদ একভাবে সংজ্ঞায়িত (পর্ব ১২ “Recursive সংজ্ঞা আর structural induction”). — recursive সংজ্ঞা
2. অনন্যতা: ধরুন a আর b দুটি ক্রমই শর্তগুলো মানে। P(n): a_n = b_n. n < k-এর জন্য P(n) সত্য, কারণ দুজনের initial condition এক। — basis
3. n ≥ k আর সব j < n-এ P(j) সত্য ধরলে a_n = ∑ c_ia_n−i = ∑ c_ib_n−i = b_n. তাই strong induction-এ সব n-এর জন্য a_n = b_n. ∎ — পর্ব ১১

এই লেমাটিই পুরো পর্বের ভিত্তি। কোনো সূত্র recurrence মানে আর প্রথম k-টি মান মেলায়, এটুকু দেখালেই সূত্রটি সব n-এর জন্য সঠিক; আলাদা induction আর লাগে না। আর উল্টো দিকে সতর্কতা: degree k-এর recurrence-এ k-এর কম initial condition দিলে উত্তর অনন্য নয়, বেশি দিলে পরস্পরবিরোধী হতে পারে।

২ · Characteristic equation — rⁿ অনুমান আর superposition

Degree 1-এর ক্ষেত্রটি সহজ: a_n = c·a_n−1 খুলে লিখলে a_n = cⁿa₀, একটি geometric progression (পর্ব ১৭ “Sequence আর summation — closed form আর বিখ্যাত যোগফল”). তাহলে degree 2-এও হয়তো সমাধান গুণোত্তর ধরনের। a_n = rⁿ (r ≠ 0) বসিয়ে দেখি a_n = c₁a_n−1 + c₂a_n−2 কখন মেটে:

rⁿ = c₁rⁿ⁻¹ + c₂rⁿ⁻² ⇔ r² − c₁r − c₂ = 0

দুই পাশকে rⁿ⁻² ≠ 0 দিয়ে ভাগ করা হয়েছে। n-এর ওপর নির্ভরতা পুরো উধাও; বাকি থাকে r-এর একটি সাধারণ দ্বিঘাত সমীকরণ।

অনুমানটি কেন যুক্তিসঙ্গত, তা degree 1 থেকেই বোঝা যায়। বাজারঘরের একটি সঞ্চয় হিসাবে প্রতি মাসে ব্যালান্স একটি নির্দিষ্ট গুণে বাড়ে, ধরুন b_n = 1.01 b_n−1 (হার কাল্পনিক, শুধু হিসাবের জন্য, কোনো আর্থিক পরামর্শ নয়)। এখানে প্রতিটি ধাপ আগের মানকে একই সংখ্যা দিয়ে গুণ করে, তাই উত্তর গুণোত্তর। Degree 2-এ ধাপটি দুটি আগের মান মেশায়, কিন্তু মেশানোর নিয়ম n-এর সঙ্গে বদলায় না; তাই এমন কোনো গুণোত্তর ক্রম খোঁজা স্বাভাবিক, যার ক্ষেত্রে দুই আগের মান মেশানো আর একটি নির্দিষ্ট সংখ্যায় গুণ করা একই কথা। আর c_k ≠ 0 শর্তটি কেন: c_k = 0 হলে recurrence আসলে ছোট degree-র, শুধু শুরুর সূচক সরানো, আর r = 0 একটি অর্থহীন “মূল” হয়ে ঢোকে।

লেখার নিয়মটি মনে রাখার একটি সহজ কৌশল: a_n−i-কে r^k−i দিয়ে বদলান, তারপর সব পদ এক পাশে আনুন। Fibonacci-র জন্য r² − r − 1 = 0; বাজারঘরের কুপনের জন্য r² − r − 2 = 0; আর a_n = 2a_n−1 − a_n−3-এর জন্য r³ − 2r² + 1 = 0 (মাঝের r-এর পদ শূন্য)। একটি সাধারণ ভুল হলো চিহ্ন উল্টে ফেলা, যেমন r² + r + 2 লেখা; মূল তখন সম্পূর্ণ আলাদা হয়।

1. (১) rⁿ = ∑ c_irⁿ⁻ⁱ-কে r^n−k ≠ 0 দিয়ে ভাগ করলে r^k = ∑ c_ir^k−i, যা ঠিক characteristic equation; প্রতিটি ধাপ উল্টানো যায়। — বীজগণিত
2. (২) αs_n + βt_n = α∑ c_is_n−i + β∑ c_it_n−i = ∑ c_i(αs_n−i + βt_n−i). অর্থাৎ নতুন ক্রমটিও একই recurrence মানে। ∎ — যোগ আর গুণের বণ্টন নিয়ম

দ্বিতীয় অংশটির নাম superposition principle. এটি ঠিক “linear” আর “homogeneous” শর্ত দুটির ফসল। Recurrence-এ + 1 থাকলে দুই সমাধানের যোগফলে + 2 আসত, তাই superposition ভাঙত; সেই ক্ষেত্রের জন্য পর্ব ৪৬ “Non-homogeneous recurrence আর particular solution” আলাদা কৌশল দেবে। এখন পরিকল্পনাটি পরিষ্কার: প্রতিটি মূল থেকে একটি গুণোত্তর সমাধান পাই, তারপর সেগুলোর linear combination নিয়ে initial condition মেলাই।

৩ · ভিন্ন মূলের উপপাদ্য — দুই মাত্রার সমাধান-জগৎ

1. (⇐) এই রূপ সমাধান: লেমা ২.২(১) অনুযায়ী r₁ⁿ আর r₂ⁿ দুটিই সমাধান, আর ২.২(২) অনুযায়ী তাদের linear combination-ও। — লেমা ২.২
2. (⇒) প্রতিটি সমাধান এই রূপের: ধরুন {a_n} একটি সমাধান। এমন α₁, α₂ খুঁজি যাতে n = 0 আর n = 1-এ মেলে: α₁ + α₂ = a₀ আর α₁r₁ + α₂r₂ = a₁. — দুই চলকের linear system
3. এই system-এর সহগ matrix [1 1; r₁ r₂]-এর determinant r₂ − r₁ ≠ 0, তাই এর ঠিক একটি সমাধান আছে। Cramer's rule থেকে α₁ = (a₀r₂ − a₁)/(r₂ − r₁) আর α₂ = (a₁ − a₀r₁)/(r₂ − r₁). — r₁ ≠ r₂
4. b_n = α₁r₁ⁿ + α₂r₂ⁿ ধাপ ১ অনুযায়ী recurrence মানে, আর ধাপ ৩ অনুযায়ী b₀ = a₀, b₁ = a₁. — নির্মাণ
5. লেমা ১.২ (অনন্যতা) অনুযায়ী সব n-এ a_n = b_n. ∎ — লেমা ১.২

ধাপ ৩-এই “ভিন্ন” শর্তটি কাজ করে: r₁ = r₂ হলে determinant শূন্য, আর system সাধারণত সমাধানহীন। তখন কী করতে হয়, তা §৫-এ। নিচের stepper বাজারঘরের কুপনের recurrence পুরোটা সমাধান করে।

1aₙ = aₙ₋₁ + 2aₙ₋₂2rⁿ বসিয়ে: r² = r + 23(r − 2)(r + 1) = 04aₙ = α₁·2ⁿ + α₂·(−1)ⁿ5α₁ + α₂ = 2, 2α₁ − α₂ = 763α₁ = 9: α₁ = 3, α₂ = −17যাচাই: a₂ = 11, a₅ = 97

এবার হিসাবরক্ষকের প্রশ্নের উত্তর এক লাইনে: ১০০ জোড় সংখ্যা, তাই (−1)¹⁰⁰ = 1, আর a₁₀₀ = 3·2¹⁰⁰ − 1 = 3802951800684688204490109616127, একটি ৩১ অঙ্কের সংখ্যা (scratch-এ recurrence চালিয়ে মেলানো)। বাস্তবে কোনো কুপন-ব্যবস্থা এভাবে চিরকাল দ্বিগুণ হয় না; মডেলটি শুধু দেখায় যে এমন নিয়ম কত দ্রুত সীমা ছাড়ায়, আর তাই রেফারেল-স্কিমে সাধারণত একটি ঊর্ধ্বসীমা রাখা হয়। গণিতের দিক থেকে মূল কথা হলো, সূত্রটি ৯৮টি যোগের বদলে একটি ঘাত আর একটি বিয়োগ চায়।

ধাপ ৬-এর উত্তর একটি জ্যামিতিক ছবিও দেয়। প্রতিটি সমাধান তার প্রথম দুটি মান (a₀, a₁) দিয়ে নির্ধারিত (লেমা ১.২), তাই সমাধানগুলোকে সমতলের বিন্দু হিসেবে ভাবা যায়। 2ⁿ-এর প্রথম দুটি মান (1, 2), আর (−1)ⁿ-এর (1, −1). এই দুটি vector সমতলের যেকোনো বিন্দুতে পৌঁছাতে পারে, কারণ তারা এক রেখায় নেই। কুপনের বিন্দু (2, 7) = 3·(1, 2) − 1·(1, −1).

নিচের ব্লক উপপাদ্যটি সাধারণভাবে প্রয়োগ করে: c₁, c₂, initial condition আর দুটি ভিন্ন মূল দিলে Cramer's rule দিয়ে α বের করে, তারপর fractions.Fraction-এ নির্ভুল ভগ্নাংশে recurrence-এর ৪০টি পদের সঙ্গে সূত্রটি মেলায়। তৃতীয় উদাহরণে মূলগুলো ভগ্নাংশ (1/2 আর 1/3), সেখানে float ব্যবহার করলে “সমান” পরীক্ষাটি বিশ্বাসযোগ্য হতো না। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from fractions import Fraction as F

def solve2(c1, c2, a0, a1, r1, r2):
    """a(n) = c1*a(n-1) + c2*a(n-2) with distinct roots r1, r2."""
    assert r1 != r2 and r1 + r2 == c1 and r1 * r2 == -c2
    det = r2 - r1                     # nonzero, because r1 != r2
    al1 = F(a0 * r2 - a1) / det       # Cramer's rule
    al2 = F(a1 - a0 * r1) / det
    return al1, al2

def iterate(c1, c2, a0, a1, N):
    a = [F(a0), F(a1)]
    for n in range(2, N):
        a.append(c1 * a[-1] + c2 * a[-2])
    return a

cases = [  # (c1, c2, a0, a1, r1, r2)
    (1, 2, 2, 7, 2, -1),
    (7, -10, 2, 1, 2, 5),
    (F(5, 6), F(-1, 6), 1, 2, F(1, 2), F(1, 3)),
]
for c1, c2, a0, a1, r1, r2 in cases:
    al1, al2 = solve2(c1, c2, a0, a1, r1, r2)
    seq = iterate(c1, c2, a0, a1, 40)
    ok = all(al1 * r1**n + al2 * r2**n == seq[n] for n in range(40))
    print(f"roots {r1}, {r2}:  a(n) = {al1}*({r1})^n + ({al2})*({r2})^n")
    print("   a(0..5) =", [str(x) for x in seq[:6]], " match n<40:", ok)

roots 2, -1:  a(n) = 3*(2)^n + (-1)*(-1)^n
   a(0..5) = ['2', '7', '11', '25', '47', '97']  match n<40: True
roots 2, 5:  a(n) = 3*(2)^n + (-1)*(5)^n
   a(0..5) = ['2', '1', '-13', '-101', '-577', '-3029']  match n<40: True
roots 1/2, 1/3:  a(n) = 10*(1/2)^n + (-9)*(1/3)^n
   a(0..5) = ['1', '2', '3/2', '11/12', '37/72', '119/432']  match n<40: True

৪ · Binet-এর সূত্র — irrational সংখ্যা থেকে পূর্ণসংখ্যা

Fibonacci ক্রম F₀ = 0, F₁ = 1, F_n = F_n−1 + F_n−2 এই কোর্সে বারবার এসেছে। পর্ব ১২-এ strong induction দিয়ে দেখানো হয়েছে, n ≥ 3-এ f(n) > αⁿ⁻², যেখানে α = (1 + √5)/2. সেখানে α কোথা থেকে এল, তা রহস্য ছিল। এখন সেটি স্বাভাবিক: α হলো Fibonacci-র characteristic equation r² − r − 1 = 0-এর বড় মূল, যার প্রচলিত নাম φ, golden ratio. উপপাদ্য ৩.১ সরাসরি একটি নির্ভুল সূত্র দেয়।

1F₀ = 0, F₁ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂2r² − r − 1 = 03φ = (1 + √5)/2, ψ = (1 − √5)/24n = 0: α + β = 05n = 1: α(φ − ψ) = 1, φ − ψ = √56Fₙ = (φⁿ − ψⁿ)/√57|ψⁿ/√5| < 1/2 ⇒ নিকটতম পূর্ণসংখ্যা

প্রমাণ stepper-এর ধাপ ২–৭: মূল দুটি ভিন্ন বলে উপপাদ্য ৩.১ রূপটি দেয়, initial condition ধ্রুবক দেয়, আর |ψⁿ/√5| < 1/2 গোল করার দাবি প্রমাণ করে। ∎ একটি সুন্দর ফল সঙ্গে আসে: F_n+1/F_n → φ, কারণ ψⁿ → 0 (এর সাধারণ রূপ §৮-এ)। আর ψ ঋণাত্মক বলে φⁿ/√5 পালা করে F_n-এর একটু ওপরে আর একটু নিচে থাকে।

সূত্রটির একটি দ্রুত ব্যবহার হলো আকার অনুমান। log₁₀ F_n ≈ n·log₁₀ φ − log₁₀ √5 ≈ 0.20899n − 0.349. তাই F₁₀₀ প্রায় 3.54 × 10²⁰ (আসল মান 354224848179261915075), আর F₁₀₀₀-এর অঙ্কসংখ্যা ⌊208.64⌋ + 1 = 209, যা §৭-এর ব্লক নির্ভুল পূর্ণসংখ্যায় মেলাবে। পরীক্ষায় “F_n-এ কয়টি অঙ্ক” ধরনের প্রশ্নে এই হিসাবই যথেষ্ট।

কম্পিউটারে সাবধান। সূত্রটি গণিতে নির্ভুল, কিন্তু কম্পিউটারের floating point সংখ্যা (IEEE 754 double) প্রায় ১৫–১৬টি দশমিক অঙ্ক রাখে। √5 নিজেই গোল করা, আর φⁿ নিলে সেই ছোট আপেক্ষিক ত্রুটি মোটামুটি n-এর অনুপাতে বাড়ে। F_n যখন 10¹⁴-এর ঘরে, তখন 10⁻¹⁵ মাপের আপেক্ষিক ত্রুটিও পরম মানে ০.৫-এর কাছে চলে যায়, আর গোল করা ভুল পূর্ণসংখ্যায় পড়ে। নিচের ব্লক ঠিক কোথায় তা ঘটে মেপে দেখায়।

from math import sqrt

fib = [0, 1]                          # exact integers
for n in range(2, 80):
    fib.append(fib[-1] + fib[-2])

phi = (1 + sqrt(5)) / 2
psi = (1 - sqrt(5)) / 2
print("phi =", phi, "  psi =", psi)
for n in (10, 30, 50, 70, 71, 75):
    approx = phi**n / sqrt(5)         # Binet without the psi term
    err = approx - fib[n]
    ok = round(approx) == fib[n]
    print(f"n={n}: F={fib[n]}  float err {err:+.2e}  round ok: {ok}")

first = next(n for n in range(80) if round(phi**n / sqrt(5)) != fib[n])
print("first n where float Binet fails:", first)
print("F(71) < 2**53 ?", fib[71] < 2**53)

phi = 1.618033988749895   psi = -0.6180339887498949
n=10: F=55  float err +3.64e-03  round ok: True
n=30: F=832040  float err +2.41e-07  round ok: True
n=50: F=12586269025  float err +1.91e-05  round ok: True
n=70: F=190392490709135  float err +4.38e-01  round ok: True
n=71: F=308061521170129  float err +6.88e-01  round ok: False
n=75: F=2111485077978050  float err +5.25e+00  round ok: False
first n where float Binet fails: 71
F(71) < 2**53 ? True

৫ · পুনরাবৃত্ত মূল — n·rⁿ কোথা থেকে আসে

a_n = 6a_n−1 − 9a_n−2 নিন। Characteristic equation r² − 6r + 9 = (r − 3)² = 0: মূল একটিই, 3, দুবার। উপপাদ্য ৩.১-এর রূপ α₁3ⁿ + α₂3ⁿ আসলে (α₁ + α₂)3ⁿ, একটিমাত্র ধ্রুবক। কিন্তু initial condition দুটি, তাই এক ধ্রুবক দিয়ে দুটি মেলানো সাধারণত অসম্ভব। একটি দ্বিতীয়, স্বাধীন সমাধান দরকার। মূলটি m বার থাকলে বলা হয় তার multiplicity m; এখানে m = 2.

1. (r − r₀)² = r² − 2r₀r + r₀²-এর সঙ্গে সহগ মিলিয়ে c₁ = 2r₀ আর c₂ = −r₀². c₂ ≠ 0 বলে r₀ ≠ 0. — সহগ তুলনা
2. n·r₀ⁿ একটি সমাধান: ডান পাশ c₁(n − 1)r₀ⁿ⁻¹ + c₂(n − 2)r₀ⁿ⁻² = 2(n − 1)r₀ⁿ − (n − 2)r₀ⁿ = n·r₀ⁿ, যা বাম পাশের সমান। — ধাপ ১ বসিয়ে
3. r₀ⁿ সমাধান (লেমা ২.২), তাই superposition-এ (α₁ + α₂n)r₀ⁿ-ও সমাধান। — লেমা ২.২(২)
4. প্রতিটি সমাধান এই রূপের: n = 0 আর n = 1 বসালে α₁ = a₀ আর (α₁ + α₂)r₀ = a₁. Determinant r₀ ≠ 0, তাই একমাত্র সমাধান α₂ = a₁/r₀ − a₀. — ধাপ ১
5. এই α-তে সূত্রটি recurrence মানে আর প্রথম দুটি মান মেলায়, তাই লেমা ১.২ অনুযায়ী সব n-এ a_n মেলে। ∎ — লেমা ১.২

কোন ক্ষেত্র কোনটি, তা আগেই চেনার একটি সহজ পরীক্ষা: r² − c₁r − c₂-এর discriminant c₁² + 4c₂. এটি ধনাত্মক হলে দুটি ভিন্ন বাস্তব মূল (উপপাদ্য ৩.১), শূন্য হলে একটি পুনরাবৃত্ত মূল r₀ = c₁/2 (উপপাদ্য ৫.১), আর ঋণাত্মক হলে দুটি complex মূল (§৬). যেমন 6² + 4(−9) = 0, তাই 6a_n−1 − 9a_n−2-এ মূল 6/2 = 3, দুবার।

n·r₀ⁿ কোথা থেকে আসে, তার একটি স্বজ্ঞা: ভিন্ন মূল r₁ আর r₀-এর জন্য (r₁ⁿ − r₀ⁿ)/(r₁ − r₀) একটি সমাধান। r₁ → r₀ করলে এই ভাগফল rⁿ-এর derivative n·r₀ⁿ⁻¹-এর দিকে যায়, যা n·r₀ⁿ-এর ধ্রুবক গুণিতক। দুটি মূল এক হয়ে যাওয়ার মুহূর্তে হারানো সমাধানটি এভাবে ফিরে আসে।

1aₙ = 6aₙ₋₁ − 9aₙ₋₂2r² − 6r + 9 = 03(r − 3)² = 0: মূল 3, দুবার4ভুল চেষ্টা: α·3ⁿ5aₙ = (α₁ + α₂n)·3ⁿ6α₁ = 1; 3(1 + α₂) = 67aₙ = (1 + n)·3ⁿ

৬ · সাধারণ degree k আর complex মূল

একই ভাবনা যেকোনো degree-তে চলে। প্রমাণের কাঠামো হুবহু এক: প্রতিটি মূল থেকে সমাধান, superposition, আর initial condition থেকে একটি k × k linear system, যার determinant অশূন্য। শেষ ধাপটির প্রমাণ (একটি সাধারণীকৃত Vandermonde determinant অশূন্য) একটু দীর্ঘ, তাই এখানে বক্তব্যটি দিচ্ছি, প্রমাণ বাদ রাখছি; পর্ব ৪৮ “Generating function — গণনাকে বীজগণিতে রূপান্তর” partial fraction দিয়ে একই ফল অন্য পথে দেখাবে।

উদাহরণ ৬.২ (তিনটি ভিন্ন মূল)। a_n = 6a_n−1 − 11a_n−2 + 6a_n−3, a₀ = 2, a₁ = 5, a₂ = 15. Characteristic equation r³ − 6r² + 11r − 6 = (r − 1)(r − 2)(r − 3) = 0. তাই a_n = α + β·2ⁿ + γ·3ⁿ, আর §৯-এর অঙ্ক ৩-এ এর system সমাধান করে পাবেন a_n = 1 − 2ⁿ + 2·3ⁿ. ঘনসমীকরণের মূল খুঁজতে পরীক্ষায় সাধারণ কৌশল হলো rational root পরীক্ষা: পূর্ণসংখ্যা সহগ আর প্রধান সহগ 1 হলে প্রতিটি পূর্ণসংখ্যা মূল ধ্রুবক পদকে ভাগ করে। এখানে ধ্রুবক পদ −6, তাই ±1, ±2, ±3, ±6 বসিয়ে দেখলেই r = 1 পাওয়া যায়, আর ভাগ করে বাকি দ্বিঘাত r² − 5r + 6.

উদাহরণ ৬.৩ (তিনগুণ মূল)। a_n = −3a_n−1 − 3a_n−2 − a_n−3, a₀ = 1, a₁ = −2, a₂ = −1. Characteristic equation r³ + 3r² + 3r + 1 = (r + 1)³: মূল −1, multiplicity 3. রূপ (α₀ + α₁n + α₂n²)(−1)ⁿ; initial condition থেকে a_n = (1 + 3n − 2n²)(−1)ⁿ.

Complex মূল। সহগ বাস্তব হলেও মূল complex number হতে পারে, আর তখন complex মূলগুলো conjugate জোড়ায় আসে। উপপাদ্যগুলো complex সংখ্যাতেও খাটে, কারণ প্রমাণে শুধু যোগ, গুণ আর ভাগ লেগেছে। বাস্তব উত্তর পেতে জোড়াটিকে একসঙ্গে লেখা হয়: মূল ρ(cos θ ± i sin θ) হলে সমাধান ρⁿ(A cos nθ + B sin nθ). ρ = 1 আর θ যদি 2π-এর একটি মূলদ ভগ্নাংশ হয়, তাহলে ক্রমটি পর্যায়বৃত্ত, একটি periodic sequence.

• a_n = −a_n−2: r² + 1 = 0, মূল ±i, θ = π/2. ক্রম প্রতি ৪ ধাপে ফেরে: a₀ = 1, a₁ = 2 থেকে 1, 2, −1, −2, 1, 2, …, অর্থাৎ a_n = cos(nπ/2) + 2 sin(nπ/2).
• a_n = a_n−1 − a_n−2: r² − r + 1 = 0, মূল (1 ± i√3)/2, θ = π/3, period 6. Complex সংখ্যা ছাড়াও এটি দেখা যায়: a_n+1 = a_n − a_n−1 আর a_n+2 = a_n+1 − a_n যোগ করলে a_n+2 = −a_n−1, অর্থাৎ a_n+3 = −a_n, তাই a_n+6 = a_n.

উদাহরণ ৬.৪ (complex মূল, পুরো সমাধান)। a_n = 2a_n−1 − 2a_n−2, a₀ = 1, a₁ = 1. Characteristic equation r² − 2r + 2 = 0, discriminant 4 − 8 = −4 < 0, মূল 1 ± i. Polar রূপে 1 ± i = √2(cos π/4 ± i sin π/4), তাই ρ = √2, θ = π/4, আর a_n = (√2)ⁿ(A cos(nπ/4) + B sin(nπ/4)). n = 0 থেকে A = 1; n = 1 থেকে √2(√2/2 + B·√2/2) = 1 + B = 1, তাই B = 0. উত্তর a_n = (√2)ⁿ cos(nπ/4): ক্রম 1, 1, 0, −2, −4, −4, 0, 8, 16, … (scratch-এ ১৩টি পদ মেলানো)। এখানে ρ > 1, তাই ক্রমটি পর্যায়বৃত্ত নয়, বরং দোলায় আর দোলনের মাপ বাড়ে: প্রতি ৪ ধাপে মান −4 গুণ হয়, কারণ (1 + i)⁴ = −4.

Complex মূলে দুটি ভুল প্রায়ই দেখা যায়। প্রথমত, শুধু বাস্তব অংশ নিয়ে লেখা, যেমন 1 ± i-কে “মূল 1” ধরে a_n = α·1ⁿ লেখা; তখন ক্রমটি ধ্রুবক হওয়ার কথা, অথচ 1, 1, 0, −2, … ধ্রুবক নয়। দ্বিতীয়ত, ρ ভুলে যাওয়া: মূলের পরম মান √2 হলে প্রতিটি পদে (√2)ⁿ গুণক লাগে, শুধু cos আর sin যথেষ্ট নয়। দুটি ভুলই প্রথম কয়েকটি পদ মেলালেই ধরা পড়ে।

বাজারঘরের সাপ্তাহিক মজুদ-সমন্বয়ের মতো কোনো হিসাব যদি এমন নিয়মে চলে, তাহলে সংখ্যাগুলো বাড়েও না, কমেও না, শুধু ঘুরে ঘুরে আসে। নিচের ব্লক §৫ আর §৬-এর প্রতিটি দাবি নির্ভুল পূর্ণসংখ্যায় মেলায়।

def iterate(coeffs, init, N):
    """a(n) = coeffs[0]*a(n-1) + coeffs[1]*a(n-2) + ..."""
    a = list(init)
    while len(a) < N:
        a.append(sum(c * a[-1 - i] for i, c in enumerate(coeffs)))
    return a

# 1) double root 3:  a(n) = 6a(n-1) - 9a(n-2),  a0 = 1, a1 = 6
seq = iterate([6, -9], [1, 6], 30)
print("a(0..6)      :", seq[:7])
print("(1 + n) 3^n  :", [(1 + n) * 3**n for n in range(7)])
print("match n<30   :", all(seq[n] == (1 + n) * 3**n for n in range(30)))
print("only alpha*3^n with alpha = 1 gives a1 =", 1 * 3, "not 6")

# 2) roots 1, 2, 3:  a(n) = 6a(n-1) - 11a(n-2) + 6a(n-3)
seq = iterate([6, -11, 6], [2, 5, 15], 30)
print("deg 3, roots 1,2,3:",
      all(seq[n] == 1 - 2**n + 2 * 3**n for n in range(30)))

# 3) triple root -1:  a(n) = -3a(n-1) - 3a(n-2) - a(n-3)
seq = iterate([-3, -3, -1], [1, -2, -1], 30)
print("triple root -1:", seq[:7],
      all(seq[n] == (1 + 3*n - 2*n*n) * (-1)**n for n in range(30)))

# 4) complex roots: periodic sequences
print("a(n) = -a(n-2)        :", iterate([0, -1], [1, 2], 12))
print("a(n) = a(n-1) - a(n-2):", iterate([1, -1], [0, 1], 13))

a(0..6)      : [1, 6, 27, 108, 405, 1458, 5103]
(1 + n) 3^n  : [1, 6, 27, 108, 405, 1458, 5103]
match n<30   : True
only alpha*3^n with alpha = 1 gives a1 = 3 not 6
deg 3, roots 1,2,3: True
triple root -1: [1, -2, -1, 8, -19, 34, -53] True
a(n) = -a(n-2)        : [1, 2, -1, -2, 1, 2, -1, -2, 1, 2, -1, -2]
a(n) = a(n-1) - a(n-2): [0, 1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0]

৭ · Vector space আর companion matrix — linear algebra-র চোখে

§৩-এর ছবিটি আসলে একটি সাধারণ সত্য। একটি নির্দিষ্ট recurrence-এর সব সমাধানের সেট S নিন। লেমা ২.২(২) বলে, S-এর দুটি ক্রমের যোগফল আর ধ্রুবক-গুণ আবার S-এ থাকে; শূন্য ক্রমও S-এ আছে। তাই S সব অসীম ক্রমের জগতের একটি vector space (subspace). Linear algebra-র এই ভাষা Machine Learning কোর্সের পর্ব ৬-এ বিস্তারিত আছে; এখানে শুধু span, basis আর dimension শব্দ তিনটি লাগবে।

1. T: S → ℝ^k, T(a) = (a₀, …, a_k−1) নিন। দুটি ক্রম যোগ করলে প্রথম k-টি মানও যোগ হয়, তাই T linear. — সংজ্ঞা
2. লেমা ১.২-এর অস্তিত্ব অংশ: প্রতিটি (a₀, …, a_k−1) থেকে একটি সমাধান হয়, তাই T onto. অনন্যতা অংশ: একই প্রথম k মান মানে একই ক্রম, তাই T one-to-one. — লেমা ১.২
3. একটি bijective linear map dimension রক্ষা করে, তাই dim S = dim ℝ^k = k. — isomorphism
4. k = 2-এ উপপাদ্য ৩.১-এর প্রমাণ দেখিয়েছে r₁ⁿ, r₂ⁿ সব S-কে span করে; k-মাত্রার জগতে k-টি span-কারী vector-ই একটি basis. ∎ — উপপাদ্য ৩.১

উপপাদ্যটির একটি ব্যবহারিক অর্থ আছে। আপনি যদি কোনোভাবে k-টি এমন সমাধান পান যাদের প্রথম k-টি মানের vector-গুলো linearly independent, তাহলে সেগুলোই basis, আর প্রতিটি সমাধান তাদের linear combination. §৩-এর ছবিতে k = 2: (1, 2) আর (1, −1) এক রেখায় নেই, তাই 2ⁿ আর (−1)ⁿ যথেষ্ট।

এই দৃষ্টিতে characteristic equation-এর পদ্ধতিটি একটি basis খোঁজা: গুণোত্তর ক্রমগুলো সবচেয়ে সুবিধার basis, কারণ তাদের ঘাত সহজে লেখা যায়। পুনরাবৃত্ত মূলে গুণোত্তর ক্রম যথেষ্ট নয়, তাই n·rⁿ যোগ করে basis পূর্ণ করতে হয়।

Companion matrix. Degree 2-এর recurrence-কে একটি 2 × 2 matrix দিয়ে এক ধাপের গুণ হিসেবে লেখা যায় (matrix গুণ পর্ব ১৯ “Discrete math-এ matrix — 0-1 matrix আর Boolean product”-এ):

[a_n; a_n−1] = C · [a_n−1; a_n−2], C = [c₁ c₂; 1 0]

তাই [a_n; a_n−1] = Cⁿ⁻¹[a₁; a₀]. C-কে বলে recurrence-এর companion matrix. এর characteristic polynomial det(rI − C) = (r − c₁)·r − c₂ = r² − c₁r − c₂: হুবহু আমাদের characteristic equation. অর্থাৎ characteristic root আসলে C-এর eigenvalue, আর প্রতিটি মূল r-এর জন্য (r, 1) একটি eigenvector (eigenvalue-র ভাবনা Machine Learning কোর্সের পর্ব ৮-এ)। মূল দুটি ভিন্ন হলে C-কে diagonal করা যায়, C = VDV⁻¹, তাই Cⁿ = VDⁿV⁻¹, আর Dⁿ-এর ঘরে r₁ⁿ, r₂ⁿ: উপপাদ্য ৩.১ আবার পাওয়া গেল। পুনরাবৃত্ত মূলে C-কে diagonal করা যায় না, আর তার Jordan রূপের ঘাতে n·rⁿ⁻¹ পদ আসে; n·rⁿ সমাধানের এটিই linear algebra-র ব্যাখ্যা।

Degree k-তেও একই গঠন: k × k companion matrix-এর প্রথম সারিতে c₁, …, c_k, আর তার নিচে একটি সরানো identity, যা প্রতিটি পুরোনো মানকে এক ঘর নিচে নামায়। যেমন উদাহরণ ৬.২-এর জন্য C = [6 −11 6; 1 0 0; 0 1 0], আর det(rI − C) = r³ − 6r² + 11r − 6. এই কারণে matrix-এর eigenvalue-র তত্ত্বের প্রতিটি ফল, যেমন ভিন্ন eigenvalue-র eigenvector-গুলো linearly independent, সরাসরি recurrence-এর ফলে অনুবাদ হয়।

1. ভিত্তি n = 1: Q = [F₂ F₁; F₁ F₀] = [1 1; 1 0]. — সরাসরি
2. ধাপ: Qⁿ⁺¹ = QⁿQ = [F_n+1 + F_n F_n+1; F_n + F_n−1 F_n] = [F_n+2 F_n+1; F_n+1 F_n]. ∎ — induction আর Fibonacci-র নিয়ম

উপপাদ্যটি থেকে Fibonacci-র অনেক অভেদ বিনা পরিশ্রমে আসে, কারণ matrix-এর ঘাতের নিয়ম Q^m+n = Q^mQⁿ সবসময় সত্য। দুই পাশের ওপরের-ডান ঘর মেলালে F_m+n = F_m+1F_n + F_mF_n−1 (m, n ≥ 1). m = n বসালে F_2n = F_n(F_n+1 + F_n−1); যেমন F₁₀ = 5 × (8 + 3) = 55. এই “দ্বিগুণ করার” সূত্র দিয়ে F_n থেকে সরাসরি F_2n-এ লাফ দেওয়া যায়, যা fast doubling নামের দ্রুত পদ্ধতির ভিত্তি।

দুই পাশের determinant নিলে (−1)ⁿ = F_n+1F_n−1 − F_n²: পর্ব ১২-এর Cassini-র সূত্র এক লাইনে। আর ব্যবহারিক লাভ: Qⁿ binary exponentiation-এ প্রায় 2 log₂ n-টি matrix গুণে পাওয়া যায়, প্রতিটি পূর্ণসংখ্যায় নির্ভুল। DSA কোর্সের পর্ব ৫২-এ memoization আর tabulation-এর আলোচনা এর সঙ্গে মিলিয়ে দেখতে পারেন।

def matmul(X, Y):
    return [[sum(X[i][k] * Y[k][j] for k in range(2)) for j in range(2)]
            for i in range(2)]

def matpow(M, n):                     # fast exponentiation: O(log n) products
    R, count = [[1, 0], [0, 1]], 0
    while n:
        if n & 1:
            R, count = matmul(R, M), count + 1
        M, count, n = matmul(M, M), count + 1, n >> 1
    return R, count

Q = [[1, 1], [1, 0]]                  # companion matrix of a(n) = a(n-1) + a(n-2)
P, used = matpow(Q, 10)
print("Q^10 =", P, "-> [[F11, F10], [F10, F9]]")

a, b = 0, 1
for _ in range(1000):
    a, b = b, a + b                   # a = F(1000) by plain iteration
P, used = matpow(Q, 1000)
print("F(1000): matrix == loop:", P[0][1] == a, " digits:", len(str(a)),
      " matrix products:", used)

# dominant root: a(n)/a(n-1) for a(n) = a(n-1) + 2a(n-2), a0=2, a1=7
s = [2, 7]
for n in range(2, 41):
    s.append(s[-1] + 2 * s[-2])
for n in (1, 5, 10, 20, 40):
    print(f"n={n}: a(n)/a(n-1) = {s[n] / s[n-1]:.10f}")

Q^10 = [[89, 55], [55, 34]] -> [[F11, F10], [F10, F9]]
F(1000): matrix == loop: True  digits: 209  matrix products: 16
n=1: a(n)/a(n-1) = 3.5000000000
n=5: a(n)/a(n-1) = 2.0638297872
n=10: a(n)/a(n-1) = 1.9980481457
n=20: a(n)/a(n-1) = 1.9999980927
n=40: a(n)/a(n-1) = 2.0000000000

৮ · বৃদ্ধির হার — dominant root

পরীক্ষায় আর অ্যালগরিদম বিশ্লেষণে প্রায়ই পুরো closed form লাগে না, শুধু জানতে চাওয়া হয় ক্রমটি কত দ্রুত বাড়ে। তখন characteristic equation-এর মূলগুলো বের করে সবচেয়ে বড় মাপের মূলটি দেখলেই বেশিরভাগ কাজ শেষ, ধ্রুবক হিসাব করার দরকার পড়ে শুধু একটি জায়গায়: তার সহগ শূন্য কি না।

a_n = 3·2ⁿ − (−1)ⁿ-এ n বড় হলে (−1)ⁿ পদটি নগণ্য, আর a_n প্রায় 3·2ⁿ. সাধারণভাবে, সবচেয়ে বড় পরম মানের মূলটিই দীর্ঘমেয়াদে সব ঠিক করে। একে বলে dominant root.

1. q = r₂/r₁ ধরুন; |q| < 1, তাই qⁿ → 0. — গুণোত্তর ধারা (পর্ব ১৭)
2. a_n/r₁ⁿ = α₁ + α₂qⁿ → α₁. — ধাপ ১
3. a_n/a_n−1 = r₁·(α₁ + α₂qⁿ)/(α₁ + α₂qⁿ⁻¹) → r₁·α₁/α₁ = r₁; এখানে α₁ ≠ 0 শর্তটি হরকে শূন্য থেকে দূরে রাখে। — সীমার নিয়ম
4. ধাপ ২ থেকে বড় n-এ |a_n| থাকে |α₁|·|r₁|ⁿ/2 আর 2|α₁|·|r₁|ⁿ-এর মধ্যে, যা Θ-এর সংজ্ঞা। ∎ — সংজ্ঞা

দুটি শর্তই সত্যিই লাগে। α₁ = 0 হলে: কুপনের একই recurrence, কিন্তু a₀ = 1, a₁ = −1 দিলে α₁ + α₂ = 1, 2α₁ − α₂ = −1 থেকে α₁ = 0, আর ক্রমটি (−1)ⁿ: কোনো বৃদ্ধিই নেই। মাপ সমান হলে: a_n = −a_n−2-এ মূল ±i, দুটিরই পরম মান 1, আর অনুপাত a_n/a_n−1 কোনো সীমায় যায় না, ঘুরতে থাকে। Fibonacci-তে φ ≈ 1.618 dominant, তাই F_n = Θ(φⁿ): naive recursive Fibonacci function-এর call সংখ্যাও এই হারে বাড়ে, যার হিসাব DSA কোর্সের পর্ব ৮-এ।

ভিন্ন মূলের সাধারণ degree k-তেও একই কথা; পুনরাবৃত্ত dominant মূলে n^m−1 গুণক যোগ হয়, যেমন (1 + n)3ⁿ = Θ(n·3ⁿ). অ্যালগরিদমের সময়ের recurrence-এ এই ধরনের Θ উত্তরই সাধারণত আসল চাওয়া, যা পর্ব ৪৭ “Divide-and-conquer recurrence আর master theorem-এর গণিত”-এ অন্য ধরনের recurrence-এ আবার দেখবেন।

৯ · পরীক্ষার অঙ্ক আর একটি ভুল সমাধান

অঙ্ক ১: ভিন্ন মূল

a_n = 7a_n−1 − 10a_n−2, a₀ = 2, a₁ = 1 সমাধান করুন।

1. r² − 7r + 10 = (r − 2)(r − 5) = 0, মূল 2 আর 5.
2. a_n = α₁2ⁿ + α₂5ⁿ; α₁ + α₂ = 2, 2α₁ + 5α₂ = 1.
3. প্রথমটির দ্বিগুণ বাদ দিলে 3α₂ = −3, তাই α₂ = −1, α₁ = 3.
4. উত্তর a_n = 3·2ⁿ − 5ⁿ; যাচাই a₂ = 7 − 20 = −13 = 12 − 25.

অঙ্ক ২: পুনরাবৃত্ত মূল

a_n = 4a_n−1 − 4a_n−2, a₀ = 3, a₁ = 10. a₅ কত?

1. r² − 4r + 4 = (r − 2)², মূল 2 দুবার; a_n = (α₁ + α₂n)2ⁿ.
2. n = 0: α₁ = 3. n = 1: 2(3 + α₂) = 10, তাই α₂ = 2.
3. a_n = (3 + 2n)2ⁿ, আর a₅ = 13 · 32 = 416. ক্রম 3, 10, 28, 72, 176, 416 recurrence থেকেও একই।

অঙ্ক ৩: degree 3

উদাহরণ ৬.২-এর a_n = α + β·2ⁿ + γ·3ⁿ-এ a₀ = 2, a₁ = 5, a₂ = 15 বসান।

1. α + β + γ = 2, α + 2β + 3γ = 5, α + 4β + 9γ = 15.
2. পরপর বিয়োগ: β + 2γ = 3 আর 2β + 6γ = 10, অর্থাৎ β + 3γ = 5.
3. আবার বিয়োগ: γ = 2, তাই β = −1 আর α = 1. উত্তর a_n = 1 − 2ⁿ + 2·3ⁿ; a₃ = 1 − 8 + 54 = 47, recurrence-এ 90 − 55 + 12 = 47.

অঙ্ক ৪: বৃদ্ধির হার আর ঋণাত্মক মূল

a_n = a_n−1 + 6a_n−2, a₀ = 1, a₁ = 0. Closed form আর বৃদ্ধির হার বলুন।

1. r² − r − 6 = (r − 3)(r + 2) = 0, মূল 3 আর −2.
2. α₁ + α₂ = 1, 3α₁ − 2α₂ = 0; প্রথমটির দ্বিগুণ যোগ করলে 5α₁ = 2, তাই α₁ = 2/5, α₂ = 3/5.
3. a_n = (2·3ⁿ + 3·(−2)ⁿ)/5; ক্রম 1, 0, 6, 6, 42, 78, 330, … (দুটি পদ সমান হতে পারে, যেমন a₂ = a₃ = 6).
4. |3| > |−2| আর α₁ = 2/5 ≠ 0, তাই উপপাদ্য ৮.১ অনুযায়ী a_n = Θ(3ⁿ), আর a_n/a_n−1 → 3.

অঙ্ক ৫: সূত্র থেকে recurrence

a_n = (2 − n)5ⁿ কোন degree 2-এর linear homogeneous recurrence মানে? মূল 5 দুবার, তাই characteristic equation (r − 5)² = r² − 10r + 25, আর recurrence a_n = 10a_n−1 − 25a_n−2, a₀ = 2, a₁ = 5.

সমাধানের ভুল ধরুন: “দুটি মূলই 3”

একজন a_n = 6a_n−1 − 9a_n−2, a₀ = 1, a₁ = 6 সমাধানে লিখলেন: “মূল r₁ = 3, r₂ = 3, তাই a_n = α₁3ⁿ + α₂3ⁿ. n = 0: α₁ + α₂ = 1. n = 1: 3α₁ + 3α₂ = 6, অর্থাৎ α₁ + α₂ = 2. সমীকরণ দুটি পরস্পরবিরোধী, তাই recurrence-টির কোনো সমাধান নেই।”

ভুল কোথায়: উপসংহারটি লেমা ১.২-এর বিরুদ্ধে যায়: প্রতিটি initial condition-এ সমাধান ঠিক একটি আছে (1, 6, 27, 108, …). ভুলটি রূপে: উপপাদ্য ৩.১ ভিন্ন মূল চায়, আর r₁ = r₂ হলে α₁3ⁿ + α₂3ⁿ আসলে এক ধ্রুবকের রূপ; system-এর determinant r₂ − r₁ = 0. সঠিক রূপ (α₁ + α₂n)3ⁿ, যা (1 + n)3ⁿ দেয় (উপপাদ্য ৫.১). শিক্ষা: “system-এর সমাধান নেই” মানে প্রায় সবসময় ভুল রূপ নেওয়া হয়েছে, recurrence-এর দোষ নয়।

১০ · AI-এর যুগে — recurrence-এর সমাধান যাচাই

Recurrence সমাধান AI সহকারীর কাছে একটি প্রিয় কাজ, আর উত্তরগুলো দেখতে নিখুঁত। কিন্তু এই বিষয়ে ভুল যাচাই করাও সবচেয়ে সহজ: সূত্রে কয়েকটি n বসিয়ে recurrence-এর পদের সঙ্গে মেলালেই হয়। নিয়মিত যে ভুলগুলো দেখা যায়:

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

• Characteristic equation-এর মূলগুলোর যোগফল আর গুণফল সহগের সঙ্গে মিলিয়েছি
• পুনরাবৃত্ত মূল থাকলে n·rⁿ পদ আছে কি না দেখেছি
• সূত্রে দেওয়া initial condition-এর সূচক বসিয়ে মান মিলিয়েছি
• অন্তত ২০–৩০টি পদ পূর্ণসংখ্যা বা Fraction-এ recurrence-এর সঙ্গে মিলিয়েছি, float-এ নয়
• ব্যবহৃত প্রতিটি উপপাদ্যের শর্ত (c_k ≠ 0, ভিন্ন মূল) লেখা আছে কি না দেখেছি
• উদ্ধৃত নাম, সাল আর উৎস বিশ্বস্ত বইয়ে মিলিয়েছি

Recurrence-এর ক্ষেত্রে একটি বড় সুবিধা আছে: লেমা ১.২ বলে, একটি সূত্র recurrence মানে আর প্রথম k-টি মান মেলায়, এটুকু দেখালেই সূত্রটি প্রমাণিত। তাই AI-এর দেওয়া যেকোনো সূত্র আপনি দুটি নির্দিষ্ট পরীক্ষায় নিজেই চূড়ান্তভাবে যাচাই করতে পারেন: সূত্রটি recurrence-এ বসিয়ে বীজগণিতে মেলানো, আর প্রথম k-টি মান মেলানো। কয়েকশো পদের সংখ্যাগত মিল এর সহায়ক প্রমাণ, বিকল্প নয়।

আরেকটি ভালো অভ্যাস হলো AI-কে উল্টো দিক থেকে প্রশ্ন করা। সমাধান চাওয়ার বদলে নিজের বের করা সূত্রটি দিয়ে জিজ্ঞেস করুন, “এটি কোন initial condition-এ ভুল হবে?” বা “একটি পুনরাবৃত্ত মূলের উদাহরণ দাও যেখানে এই পদ্ধতি ব্যর্থ হয়।” ভুল যুক্তি সাধারণত নির্দিষ্ট উদাহরণের সামনে টেকে না, আর উদাহরণটি আপনি নিজেই Python-এ চালিয়ে যাচাই করতে পারেন। মনে রাখবেন, AI-এর উত্তর শেখার সহায়ক, প্রমাণের উৎস নয়: চূড়ান্ত দায়িত্ব থাকে লেমা ১.২-এর মতো যাচাইযোগ্য যুক্তির ওপর।