Recurrence দিয়ে মডেল — Fibonacci, Hanoi আর bit string

১ · Recurrence relation — সংজ্ঞা, initial condition আর অনন্যতা

মডিউল ৭-এ আমরা সম্ভাবনা গুনেছি। এই মডিউলের নাম “উন্নত গণনা”, আর তার প্রথম হাতিয়ার একটি পুরোনো চেনা জিনিস: নিজের ছোট রূপ দিয়ে নিজেকে লেখা। পর্ব ১২ “Recursive সংজ্ঞা আর structural induction”-এ আপনি factorial, Fibonacci আর gcd-এর recursive সংজ্ঞা দেখেছেন। এই পর্বে প্রশ্নটি উল্টো দিক থেকে আসে: একটি গণনার সমস্যা হাতে, যার সরাসরি সূত্র চোখে পড়ে না। তাকে কীভাবে “আগের ধাপের উত্তর দিয়ে এই ধাপের উত্তর” আকারে লেখা যায়? এই লেখাটিই একটি মডেল।

শুধু recurrence একটি ধারাকে ঠিক করে না। a_n = a_n−1 + a_n−2-এর একটি সমাধান Fibonacci ধারা 0, 1, 1, 2, 3, 5, 8, …, আবার আরেকটি সমাধান 2, 1, 3, 4, 7, 11, 18, …, যার নাম Lucas সংখ্যা. 0, 0, 0, … ধারাটিও একটি সমাধান। একই নিয়ম, ভিন্ন শুরু, সম্পূর্ণ ভিন্ন ধারা। তাই recurrence লিখলেই কাজ শেষ নয়; initial condition আর কোন n থেকে নিয়মটি খাটে, দুটিই লিখতে হয়।

1. অস্তিত্ব: প্রথম k-টি পদ c_i, আর n ≥ k-এর জন্য a_n-কে নিয়মটি দিয়েই সংজ্ঞায়িত করুন। ডান পাশে শুধু আগের পদ আছে, তাই এটি একটি বৈধ recursive সংজ্ঞা। — recursive সংজ্ঞা (পর্ব ১২)
2. অনন্যতা, প্রস্তুতি: ধরুন a আর b দুটি ধারাই সব শর্ত মানে। দাবি P(n): a_n = b_n. — প্রমাণের লক্ষ্য
3. ভিত্তি: 0 ≤ n ≤ k − 1 হলে a_n = c_n = b_n. — initial condition
4. ধাপ: n ≥ k, আর ধরুন সব m < n-এ P(m) সত্য। তাহলে a_n = f(n, a_n−1, …, a_n−k) = f(n, b_n−1, …, b_n−k) = b_n, কারণ মাঝের সমতায় প্রতিটি সূচক n − 1, …, n − k ছোট। — strong induction-এর অনুমান
5. পর্ব ১১-এর strong induction অনুযায়ী সব n ≥ 0-এ a_n = b_n. ∎ — strong induction

ধাপ ৪-এ লক্ষ করুন, একসঙ্গে k-টি আগের পদ লাগে, তাই সাধারণ induction নয়, strong induction স্বাভাবিক পছন্দ। আর ধাপ ৩-এ ঠিক k-টি ভিত্তি লাগে: order 2-এর recurrence-এ শুধু a₀ দিলে a₁ যেকোনো মান নিতে পারে, আর প্রতিটি মান একটি আলাদা সমাধান দেয়। উল্টো দিকে, বেশি initial condition দিলে তারা পরস্পরবিরোধী হতে পারে: a₀ = 0, a₁ = 1, a₂ = 5 আর a_n = a_n−1 + a_n−2 (n ≥ 2) একসঙ্গে কোনো ধারা মানে না।

২ · প্রথম মডেল — বাজারঘরের ঋণ আর মাসিক জমা

বাজারঘর নতুন গুদামের তাক কিনতে ১০ লাখ টাকা ঋণ নিল। ধরা যাক মাসে 1% হারে সুদ যোগ হয়, আর প্রতি মাসের শেষে একটি নির্দিষ্ট কিস্তি P শোধ করা হয়। সুদের হারটি শুধু হিসাব বোঝানোর একটি কাল্পনিক সংখ্যা; বাস্তব ঋণের শর্ত, ফি আর গোলাকরণের নিয়ম আলাদা, আর এটি কোনো আর্থিক পরামর্শ নয়। প্রশ্ন: n মাস পরে বাকি কত, আর ১২ মাসে শোধ করতে P কত হওয়া উচিত?

B_n = n মাস পরে বাকি টাকা ধরুন। মাস শুরুর বাকি B_n−1-এর ওপর সুদ যোগ হয়ে (1 + r)B_n−1 হয়, তারপর P বাদ যায়। তাই মডেল:

B₀ = 1000000,   B_n = (1 + r)B_n−1 − P   (n ≥ 1),   r = 1/100

এটি order 1-এর recurrence, একটি initial condition যথেষ্ট। এখানে compound interest বা চক্রবৃদ্ধি সুদ লুকিয়ে আছে: সুদের ওপরও সুদ ধরে। এবার unrolling (iteration) করি, অর্থাৎ নিয়মটি বারবার নিজের ভেতরে বসাই। g = 1 + r লিখলে

B_n = gB_n−1 − P = g²B_n−2 − gP − P = … = gⁿB₀ − P(gⁿ⁻¹ + … + g + 1)

বন্ধনীর ভেতরটি একটি geometric series, যার যোগফল (gⁿ − 1)/(g − 1) (পর্ব ১৭ “Sequence আর summation — closed form আর বিখ্যাত যোগফল”)। এভাবে একটি অনুমান পাওয়া গেল। অনুমান প্রমাণ নয়, তাই induction লাগে।

1. ভিত্তি n = 0: ডান পাশ g⁰B₀ − P · 0/r = B₀. — সরাসরি
2. অনুমান: কোনো n ≥ 1-এর জন্য B_n−1 = gⁿ⁻¹B₀ − P(gⁿ⁻¹ − 1)/r. — inductive hypothesis
3. ধাপ: B_n = gB_n−1 − P = gⁿB₀ − P(gⁿ − g)/r − P = gⁿB₀ − P(gⁿ − g + r)/r. — recurrence আর অনুমান
4. g − r = 1, তাই gⁿ − g + r = gⁿ − 1, আর B_n = gⁿB₀ − P(gⁿ − 1)/r. ∎ — বীজগণিত, পর্ব ১০

১২ মাসে শোধ মানে B₁₂ = 0. সূত্রে বসিয়ে P = rB₀g¹²/(g¹² − 1). এই পদ্ধতিতে সমান কিস্তিতে ঋণ শোধকে বলে amortization. একই ছাঁচে উল্টো কাজও চলে: প্রতি মাসে 5000 টাকা জমা আর মাসে 1% লাভ ধরলে S₀ = 0, S_n = (1 + r)S_n−1 + 5000, আর একই unrolling থেকে S_n = 5000(gⁿ − 1)/r; ১২ মাসে প্রায় 63412.52 টাকা (scratch-এ যাচাই করা)। নিচের ব্লক ঋণের মডেলটি Fraction দিয়ে নির্ভুলভাবে চালায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from fractions import Fraction

B0 = Fraction(1_000_000)             # loan in taka (example only)
r = Fraction(1, 100)                 # 1% per month, illustrative
N = 12
P = B0 * r / (1 - (1 + r) ** -N)     # payment that clears the loan in N months
print("exact payment P =", round(float(P), 4), "taka per month")

def closed(n):                       # the unrolled formula
    g = (1 + r) ** n
    return g * B0 - P * (g - 1) / r

B = B0
for n in range(1, N + 1):
    B = (1 + r) * B - P              # B(n) = (1 + r) B(n-1) - P
    assert B == closed(n)            # exact equality, no rounding
    if n in (1, 2, 3, 6, 11, 12):
        print(f"month {n:2}: balance {float(B):11.2f}")
print("recurrence == closed form for all", N, "months")

for pay in (88848, 88849):           # payment rounded to whole taka
    Bq = B0
    for n in range(N):
        Bq = (1 + r) * Bq - pay
    print(f"pay {pay}: after 12 months {float(Bq):7.2f}")
print("total interest:", round(float(N * P - B0), 2))

exact payment P = 88848.7887 taka per month
month  1: balance   921151.21
month  2: balance   841513.93
month  3: balance   761080.29
month  6: balance   514921.06
month 11: balance    87969.10
month 12: balance        0.00
recurrence == closed form for all 12 months
pay 88848: after 12 months   10.00
pay 88849: after 12 months   -2.68
total interest: 66185.46

এই ধরনের order 1-এর recurrence, যেখানে প্রতিবার একই ধ্রুবক যোগ বা বিয়োগ হয়, তার সাধারণ সমাধানের পদ্ধতি পর্ব ৪৬ “Non-homogeneous recurrence আর particular solution”-এ আসবে। আজ আমরা unrolling দিয়ে অনুমান আর induction দিয়ে প্রমাণের পথেই থাকব।

৩ · Fibonacci-র খরগোশ, ছন্দ আর “00”-হীন bit string

পিসার Leonardo, পরে যিনি Fibonacci নামে পরিচিত, ১২০২ সালের Liber Abaci বইয়ে একটি খরগোশের ধাঁধা দেন। আধুনিক পাঠ্যবইয়ে মডেলটি সাধারণত এভাবে বলা হয়: প্রথম মাসে একটি সদ্যোজাত জোড়া; প্রতিটি জোড়া জন্মের দ্বিতীয় মাস থেকে প্রতি মাসে একটি নতুন জোড়ার জন্ম দেয়; কোনো খরগোশ মরে না। R_n = n-তম মাসে জোড়ার সংখ্যা।

1. n-তম মাসের জোড়া দুই দলে পড়ে: আগের মাসেও যারা ছিল (R_n−1টি), আর এই মাসে যারা জন্মাল।
2. এই মাসে জন্ম দেয় ঠিক সেই জোড়াগুলো, যারা অন্তত দুই মাস আগে থেকে আছে, অর্থাৎ R_n−2টি।
3. তাই R_n = R_n−1 + R_n−2 (n ≥ 3), R₁ = R₂ = 1; বারো মাসে R₁₂ = 144.

মডেলটি জীববিজ্ঞান হিসেবে অবাস্তব: খরগোশ মরে, একবারে একাধিক বাচ্চা হয়। কিন্তু গণিতের দিক থেকে এর অনুমানগুলো স্পষ্ট, আর অনুমান স্পষ্ট বলেই কোথায় বাস্তবের সঙ্গে মেলে না, তা দেখানো যায়। ভালো মডেলের এটিই প্রথম গুণ। ইতিহাসের একটি সতর্কতা: ধারাটি এর আগেই ভারতীয় ছন্দশাস্ত্রে দেখা যায় বলে ইতিহাসবিদরা উল্লেখ করেন, Virahanka, Gopala আর Hemachandra-র নামের সঙ্গে; সঠিক তারিখ নিয়ে সূত্রভেদ আছে, পর্ব ১২-এর আলোচনাটি দেখুন।

ছন্দের প্রশ্নটি এই: ছোট মাত্রা (দৈর্ঘ্য 1) আর বড় মাত্রা (দৈর্ঘ্য 2) দিয়ে মোট n মাত্রার কয়টি ছন্দ বানানো যায়? শেষ মাত্রাটি ছোট হলে বাকি n − 1, বড় হলে বাকি n − 2; তাই m_n = m_n−1 + m_n−2, m₁ = 1, m₂ = 2. এটি আসলে n-কে 1 আর 2-এর ক্রমযুক্ত যোগফলে লেখার সংখ্যা, যাকে পর্ব ৩৭ “গণনার কৌশল — lattice path, bijection আর double counting” composition বলেছে। সেকশন ১-এর সিঁড়ির ধাঁধাও হুবহু এটি।

পর্ব ৩৭-এ আপনি প্রমাণ দেখেছেন যে দৈর্ঘ্য n-এর যে bit string-এ পরপর দুটি 0 (“00”) নেই, তার সংখ্যা a_n = a_n−1 + a_n−2, a₁ = 2, a₂ = 3, অর্থাৎ a_n = F_n+2: শেষ bit 1 হলে আগের অংশ যেকোনো বৈধ string, শেষ bit 0 হলে তার আগে অবশ্যই 1. সেই প্রমাণ আবার করছি না; দুটি নতুন দিক দেখি।

• “11”-হীন string: প্রতিটি bit উল্টে দিলে (0 ↔ 1) “00”-হীন string ঠিক “11”-হীন string হয়ে যায়, আর উল্টানো একটি bijection (পর্ব ১৬)। তাই গণনাও একই, কোনো নতুন recurrence লাগে না। বাজারঘরের ভাষায়: যদি নিয়ম হয় রাইডার পরপর দুই দিন রাতের শিফটে থাকবেন না, সূচির সংখ্যা আগের মতোই।
• বড় নিষেধ, বড় order: “000” নিষিদ্ধ হলে শেষে থাকতে পারে 1, 10 বা 100; তিন দল, তাই a_n = a_n−1 + a_n−2 + a_n−3, order 3, আর তিনটি initial condition লাগে। অনুশীলন ১-এ এর প্রমাণ আছে।

লক্ষ করুন, খরগোশ, ছন্দ, সিঁড়ি আর bit string, চারটি ভিন্ন গল্প একই recurrence দেয়, শুধু initial condition আর সূচক একটু সরে যায়: R_n = F_n, m_n = F_n+1, a_n = F_n+2. উপপাদ্য ১.২ ঠিক এই কথাটিই নিশ্চিত করে: recurrence আর initial condition মিললে ধারা মিলবেই, তাই দুটি গল্পের সম্পর্ক প্রমাণ করতে প্রতিটি পদ মেলানোর দরকার নেই।

৪ · Tower of Hanoi — recurrence, unrolling আর সর্বনিম্নতার প্রমাণ

ফরাসি গণিতবিদ Édouard Lucas ১৮৮৩ সালে একটি খেলনা-ধাঁধা বাজারে আনেন বলে জানা যায়, যার নাম Tower of Hanoi. তিনটি খুঁটি A, B, C; A-তে n-টি চাকতি, বড়টি নিচে, ছোটটি ওপরে। নিয়ম: একবারে একটি চাকতি সরানো যায়, শুধু কোনো খুঁটির সবচেয়ে ওপরেরটি, আর কখনো বড় চাকতি ছোটটির ওপর রাখা যায় না। সব চাকতি C-তে নিতে সবচেয়ে কম কয়টি চাল লাগে?

মডেল। সবচেয়ে বড় চাকতিটি (n নম্বর) C-তে নিতে হলে তার ওপরের n − 1টি চাকতি আগে সরাতে হবে, আর C-তেও রাখা যাবে না, তাই সেগুলো যাবে B-তে। কৌশলটি: (১) ওপরের n − 1টি A থেকে B-তে, C-কে সহায়ক ধরে; (২) বড় চাকতিটি A থেকে C-তে, এক চাল; (৩) n − 1টি B থেকে C-তে। H(n) = এই কৌশলে চালের সংখ্যা হলে

H(0) = 0,   H(n) = 2H(n − 1) + 1   (n ≥ 1)

H(1) = 1, H(2) = 3, H(3) = 7, H(4) = 15. প্যাটার্নটি 2ⁿ − 1-এর মতো দেখায়। Unrolling দিয়ে অনুমানটি কোথা থেকে আসে, নিচের stepper ধাপে ধাপে দেখায়।

1H(n) = 2H(n−1) + 12= 4H(n−2) + 2 + 13= 8H(n−3) + 4 + 2 + 14= 2ᵏH(n−k) + 2ᵏ − 15k = n: 2ⁿ · 0 + 2ⁿ − 16প্রমাণ: induction

এখনো একটি বড় ফাঁক আছে। আমরা দেখালাম একটি কৌশল 2ⁿ − 1 চালে কাজ সারে। কিন্তু হয়তো আরও চতুর কোনো কৌশল আছে? “সবচেয়ে কম” দাবি করতে একটি lower bound লাগে: প্রমাণ করতে হবে যে যেকোনো বৈধ সমাধানে অন্তত এতগুলো চাল লাগে।

1. ওপরের সীমা: ওপরের কৌশল H(n) = 2ⁿ − 1 চালে কাজ করে, তাই M(n) ≤ 2ⁿ − 1. — stepper
2. নিচের সীমা, induction: M(0) = 0. ধরুন n ≥ 1, আর M(n − 1) ≥ 2ⁿ⁻¹ − 1. যেকোনো একটি বৈধ সমাধান নিন। — induction
3. বড় চাকতিটি অন্তত একবার সরবেই। তার প্রথম চালের মুহূর্তে সে নিজের খুঁটির সবচেয়ে ওপরে, আর যে খুঁটিতে যাচ্ছে সেটি খালি (নইলে ছোট চাকতির ওপর বড়টি পড়ত)। তাই বাকি n − 1টি চাকতি তখন তৃতীয় খুঁটিতে একটি স্তূপ হয়ে আছে। — নিয়ম
4. শুরুতে সেই n − 1টি ছিল A-তে। বড় চাকতিটি তাদের কোনো চালে বাধা দেয় না (যেকোনো ছোট চাকতি তার ওপর বসতে পারে), তাই প্রথম চালের আগের ছোট চাকতির চালগুলো নিজেরাই n − 1 চাকতির স্তূপ সরানোর একটি বৈধ সমাধান: অন্তত M(n − 1)টি চাল। — অনুমান
5. একইভাবে বড় চাকতির শেষ চালের মুহূর্তে বাকি n − 1টি একটি অন্য খুঁটিতে স্তূপ হয়ে আছে, আর সেখান থেকে C-তে বড়টির ওপর আসতে আবার অন্তত M(n − 1)টি চাল। — একই যুক্তি
6. ধাপ ৪-এর চালগুলো প্রথম বড়-চালের আগে, ধাপ ৫-এর গুলো শেষ বড়-চালের পরে, তাই তারা আলাদা; সঙ্গে বড়টির অন্তত একটি চাল। মোট ≥ 2M(n − 1) + 1 ≥ 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1. — যোগের নিয়ম
7. দুই সীমা মিলিয়ে M(n) = 2ⁿ − 1. ∎ — ধাপ ১, ৬

ধাপ ৬-এর যুক্তি শুধু সংখ্যা দেয় না, কাঠামোও দেয়: সর্বনিম্ন সমাধানে বড় চাকতি ঠিক একবার সরে, আর সমাধানটি আসলে একটিই। Lucas-এর বিপণনে একটি “৬৪টি সোনার চাকতির মন্দির” গল্প ছিল বলে জানা যায়, যা বানানো কিংবদন্তি, কোনো বাস্তব প্রথা নয়। 64টি চাকতিতে 2⁶⁴ − 1 = 18446744073709551615টি চাল; সেকেন্ডে একটি চালে প্রায় 5.85 × 10¹¹ বছর। Hanoi-র recursive কোড আর call stack DSA কোর্সের পর্ব ০৭-এ আছে; এখানে আমাদের বিষয় সংখ্যাটির প্রমাণ।

৫ · Domino দিয়ে টালি — 2 × n আর 3 × n

বাজারঘরের ডেলিভারি ভ্যানের মেঝে 2 × n ঘরের একটি লম্বা পাটাতন, যাকে 1 × 2 মাপের একই রকম বাক্স দিয়ে পুরো ঢাকতে হবে, কোনো ফাঁক বা ওপরে-ওপরে না রেখে। প্রতিটি বাক্স খাড়া (দুই সারি জুড়ে) বা শোয়া (এক সারিতে দুই ঘর) বসতে পারে। কয়টি ভিন্ন বিন্যাস সম্ভব? এ ধরনের ঢাকাকে বলে domino tiling. নিচের ছবি মূল যুক্তিটি দেখায়।

1t(1) = 1, t(2) = 22বাঁ-ওপরের ঘর: খাড়া3বাঁ-ওপরের ঘর: শোয়া4t(n) = t(n−1) + t(n−2)5t(3), t(4), t(5)6t(n) = F(n+1)

খাড়া domino = দৈর্ঘ্য 1-এর একটি অংশ, শোয়া জোড়া = দৈর্ঘ্য 2-এর অংশ ধরলে প্রতিটি টালি-বিন্যাস n-কে 1 আর 2-এর ক্রমযুক্ত যোগফলে লেখার একটি উপায়: সেকশন ৩-এর ছন্দের সঙ্গে একটি bijection. একই উত্তর তাই আশ্চর্য নয়।

3 × n বোর্ড, সংক্ষেপে। এখানে বাঁ কলামের তিনটি ঘর ঢাকার উপায় বেশি, আর একটি নতুন জিনিস আসে: n বিজোড় হলে ঘর 3n বিজোড়, অথচ প্রতিটি domino দুটি ঘর ঢাকে, তাই কোনো টালি নেই। জোড় n-এ শেষ কলাম ধরে একটু বেশি ক্ষেত্রভাগ করলে (একটি সহায়ক ধারা নিয়ে, যা এক কোণ খালি বোর্ড গোনে) পাওয়া যায় u(0) = 1, u(2) = 3, আর জোড় n ≥ 4-এ u(n) = 4u(n − 2) − u(n − 4). প্রমাণটি এখানে বাদ রাখছি; নিচের brute force সংখ্যাগুলো মিলিয়ে দেখায়, আর এ ধরনের recurrence কীভাবে সমাধান হয় তা পর্ব ৪৫ “Linear recurrence সমাধান — characteristic equation”-এ আসবে।

def count_tilings(rows, cols):
    """Brute force: cover the first empty cell, try both dominoes."""
    grid = [[False] * cols for _ in range(rows)]
    def go():
        for c in range(cols):
            for r in range(rows):
                if grid[r][c]:
                    continue
                total = 0
                if r + 1 < rows and not grid[r + 1][c]:      # vertical
                    grid[r][c] = grid[r + 1][c] = True
                    total += go()
                    grid[r][c] = grid[r + 1][c] = False
                if c + 1 < cols and not grid[r][c + 1]:      # horizontal
                    grid[r][c] = grid[r][c + 1] = True
                    total += go()
                    grid[r][c] = grid[r][c + 1] = False
                return total
        return 1                                             # board is full
    return go()

t = {1: 1, 2: 2}
for n in range(3, 13):
    t[n] = t[n - 1] + t[n - 2]                  # 2 x n
u = {0: 1, 2: 3}
for n in range(4, 13, 2):
    u[n] = 4 * u[n - 2] - u[n - 4]              # 3 x n, n even

print(" n  2xn brute recur | 3xn brute recur")
for n in range(1, 13):
    print(f"{n:2} {count_tilings(2, n):9} {t[n]:5} |"
          f" {count_tilings(3, n):9} {u.get(n, 0):5}")

 n  2xn brute recur | 3xn brute recur
 1         1     1 |         0     0
 2         2     2 |         3     3
 3         3     3 |         0     0
 4         5     5 |        11    11
 5         8     8 |         0     0
 6        13    13 |        41    41
 7        21    21 |         0     0
 8        34    34 |       153   153
 9        55    55 |         0     0
10        89    89 |       571   571
11       144   144 |         0     0
12       233   233 |      2131  2131

৬ · সমতলে রেখা আর Catalan-এর recurrence

একটি কাগজে n-টি সরলরেখা আঁকলে কাগজটি (অসীম সমতল ধরুন) সর্বোচ্চ কয়টি অংশে ভাগ হয়? একটি রেখায় ২ ভাগ, দুটিতে ৪ ভাগ। এখানে থেমে “প্রতিবার দ্বিগুণ, তাই 2ⁿ” বলে ফেলা সহজ, আর ভুল: তিনটি রেখায় সর্বোচ্চ ৭ ভাগ, ৮ নয় (নিচের ছবি)। “সর্বোচ্চ” পেতে রেখাগুলো general position-এ থাকতে হয়: কোনো দুটি সমান্তরাল নয়, আর কোনো তিনটি এক বিন্দু দিয়ে যায় না।

1. প্রথম n − 1টি রেখা আঁকা আছে, অংশ L(n − 1)টি। n-তম রেখাটি কোনোটির সমান্তরাল নয়, তাই প্রত্যেকটিকে ঠিক একবার কাটে: n − 1টি ছেদবিন্দু। — সমান্তরাল নয়
2. কোনো তিনটি রেখা এক বিন্দুতে মেলে না, তাই এই n − 1টি বিন্দু আলাদা। তারা নতুন রেখাকে n-টি টুকরোতে ভাগ করে: দুই প্রান্তে দুটি অসীম রশ্মি আর মাঝে n − 2টি রেখাংশ। — এক বিন্দুতে তিনটি নয়
3. প্রতিটি টুকরো পুরোনো একটি অংশের ভেতর দিয়ে এক প্রান্ত থেকে আরেক প্রান্তে যায়, আর সেই অংশটিকে দুই ভাগ করে। তাই ঠিক n-টি নতুন অংশ যোগ হয়: L(n) = L(n − 1) + n. — গোনা
4. Unrolling: L(n) = 1 + (1 + 2 + … + n) = 1 + n(n + 1)/2, Gauss-এর যোগফল (পর্ব ১৭); induction-এ যাচাই সরাসরি: 1 + (n − 1)n/2 + n = 1 + n(n + 1)/2. ∎ — পর্ব ১৭, ১০

সূত্রটিকে 1 + n + C(n, 2) হিসেবেও লেখা যায়: প্রথম 1 শুরুর অংশ, প্রতিটি রেখা একটি নতুন অংশ শুরু করে (n), আর প্রতিটি ছেদবিন্দু একটি করে (C(n, 2)টি বিন্দু)। এই দ্বিতীয় দৃষ্টিভঙ্গি পরে গ্রাফের Euler সূত্রে কাজে আসবে। নিচের ব্লক Hanoi আর রেখার দুই recurrence-কে তাদের closed form-এর সঙ্গে মেলায়, আর Hanoi-র আসল চালগুলোও তৈরি করে গোনে।

from math import comb

def hanoi(n, src="A", via="B", dst="C", moves=None):
    if moves is None:
        moves = []
    if n > 0:
        hanoi(n - 1, src, dst, via, moves)   # n-1 disks out of the way
        moves.append((n, src, dst))          # the largest disk, once
        hanoi(n - 1, via, src, dst, moves)   # n-1 disks back on top
    return moves

print("3 disks:", " ".join(f"{d}:{a}>{b}" for d, a, b in hanoi(3)))

H = [0]                                      # H(0) = 0 moves
L = [1]                                      # L(0) = 1 region
for n in range(1, 21):
    H.append(2 * H[-1] + 1)                  # H(n) = 2H(n-1) + 1
    L.append(L[-1] + n)                      # L(n) = L(n-1) + n

print(" n  H(n) moves 2^n-1 | L(n) n(n+1)/2+1 1+n+C(n,2)")
for n in (1, 2, 3, 5, 8, 10):
    print(f"{n:2} {H[n]:5} {len(hanoi(n)):5} {2**n - 1:6} |"
          f" {L[n]:4} {n*(n+1)//2 + 1:9} {1 + n + comb(n, 2):9}")
print("n <= 20 all agree:",
      all(H[n] == 2**n - 1 and L[n] == n*(n+1)//2 + 1 for n in range(21)))
print("H(64) =", 2**64 - 1)

3 disks: 1:A>C 2:A>B 1:C>B 3:A>C 1:B>A 2:B>C 1:A>C
 n  H(n) moves 2^n-1 | L(n) n(n+1)/2+1 1+n+C(n,2)
 1     1     1      1 |    2         2         2
 2     3     3      3 |    4         4         4
 3     7     7      7 |    7         7         7
 5    31    31     31 |   16        16        16
 8   255   255    255 |   37        37        37
10  1023  1023   1023 |   56        56        56
n <= 20 all agree: True
H(64) = 18446744073709551615

Catalan-এর recurrence — binary tree ভাগ করে

বাজারঘরের সার্চ ইঞ্জিন পণ্যের id একটি binary tree-এ রাখে: প্রতিটি node-এর একটি বাঁ আর একটি ডান subtree, যেকোনোটি খালি হতে পারে। n-টি node-এর কতগুলো ভিন্ন আকারের binary tree আছে? পর্ব ৩৭-এ reflection দিয়ে প্রমাণ হয়েছে উত্তরটি Catalan সংখ্যা C_n = C(2n, n)/(n + 1). এখানে recurrence-এর পথে একই সংখ্যায় পৌঁছাই।

1. n + 1টি node-এর tree-তে একটি root, আর বাকি n-টি বাঁ আর ডান subtree-তে ভাগ হয়। বাঁ দিকে i-টি হলে ডানে n − i-টি, যেখানে 0 ≤ i ≤ n. — গঠন
2. i ঠিক করলে বাঁ subtree C_i উপায়ে আর ডানটি স্বাধীনভাবে C_n−i উপায়ে বাছা যায়, আর ভিন্ন বাছাই ভিন্ন tree দেয়: C_iC_n−iটি। — গুণের নিয়ম
3. ভিন্ন i-এর tree-গুলো আলাদা (বাঁ subtree-এর আকার ভিন্ন), তাই সব i যোগ করলে C_n+1 = ∑ C_iC_n−i. ∎ — যোগের নিয়ম

এখান থেকে C₁ = 1, C₂ = 2, C₃ = 5, C₄ = 14, C₅ = 42, যা C(2n, n)/(n + 1)-এর সঙ্গে মেলে (scratch-এ n ≤ 10 পর্যন্ত মেলানো)। এই recurrence-এর order নির্দিষ্ট নয়: C_n+1 আগের সব পদের ওপর নির্ভর করে। তাই এটি “full history” recurrence, আর তবু উপপাদ্য ১.২-এর একই strong induction যুক্তিতে একটি initial condition C₀ = 1 থেকেই পুরো ধারা অনন্যভাবে ঠিক হয়। এর generating function দিয়ে closed form পাওয়ার কৌশল পর্ব ৪৮ “Generating function — গণনাকে বীজগণিতে রূপান্তর”-এ আসবে।

৭ · Josephus সমস্যা — binary-তে লুকানো উত্তর

বাজারঘরের অফিসে n জন কর্মী বৃত্তাকারে বসে, নম্বর 1 থেকে n. ঈদের উপহার-লটারির একটি মজার নিয়ম: 1 নম্বর থেকে গোনা শুরু, প্রথম জন থাকেন, পরের জন বাদ যান, তার পরের জন থাকেন, তার পরের জন বাদ, এভাবে বৃত্তে ঘুরে ঘুরে প্রতি দ্বিতীয় জন বাদ যান। শেষে যিনি একা থাকেন, তিনি বড় উপহারটি পান। কোন নম্বরে বসলে জেতা যায়? এটি Josephus সমস্যা; বিজয়ীর নম্বর J(n).

1বৃত্তে 1 … 102বাদ: 2, 43বাদ: 6, 84বাদ: 10, চক্র শেষ5বাদ: 3, 76বাদ: 17বাদ: 9, বিজয়ী 58যাচাই: 1010 → 0101

1. জোড় 2n জন: প্রথম চক্রে 2, 4, …, 2n বাদ যান, আর পালা আবার 1-এর। বাকিরা 1, 3, …, 2n − 1: n জনের একটি নতুন খেলা, যার k-তম আসন আসলে 2k − 1 নম্বর। সেই খেলার বিজয়ী J(n)-তম আসন, তাই J(2n) = 2J(n) − 1. — নতুন নামকরণ
2. বিজোড় 2n + 1 জন: 2, 4, …, 2n বাদের পর পালা 2n + 1-এর, তিনি থাকেন, আর 1 বাদ যান। বাকিরা 3, 5, …, 2n + 1, শুরু 3 থেকে: k-তম আসন 2k + 1 নম্বর। তাই J(2n + 1) = 2J(n) + 1. ∎ — একই যুক্তি

এটি একটি divide-and-conquer ধরনের recurrence: n থেকে সরাসরি প্রায় n/2-তে নামে, তাই J(n) হিসাবে মাত্র প্রায় log₂ n ধাপ লাগে। ছোট মানগুলো লিখলে একটি প্যাটার্ন চোখে পড়ে: J(1..8) = 1; 1, 3; 1, 3, 5, 7; 1. প্রতিটি 2-এর ঘাতে আবার 1, তারপর 2 করে বাড়ে।

1. m-এর ওপর induction. ভিত্তি m = 0: n = 1, l = 0, আর J(1) = 1 = 2 · 0 + 1. — ভিত্তি
2. অনুমান: m ≥ 1, আর 2^m−1 + l′ আকারের প্রতিটি সংখ্যায় (0 ≤ l′ < 2^m−1) সূত্রটি সত্য। — inductive hypothesis
3. l জোড়: n = 2(2^m−1 + l/2), আর l/2 < 2^m−1. উপপাদ্য ৭.১-এ J(n) = 2J(2^m−1 + l/2) − 1 = 2(2 · l/2 + 1) − 1 = 2l + 1. — J(2n) নিয়ম
4. l বিজোড়: n = 2(2^m−1 + (l − 1)/2) + 1, তাই J(n) = 2(2 · (l − 1)/2 + 1) + 1 = 2(l − 1) + 2 + 1 = 2l + 1. ∎ — J(2n + 1) নিয়ম

Binary-র চমক। n = 2^m + l-এর binary রূপ হলো একটি 1, তারপর l-এর m-bit রূপ। 2l + 1 মানে l-কে এক ঘর বাঁয়ে সরিয়ে শেষে 1 বসানো। অর্থাৎ J(n) পেতে n-এর binary-র প্রথম 1-টি তুলে শেষে বসান: 100 = 1100100 → 1001001 = 73. নিচের ব্লক simulation, recurrence আর binary-র তিন পথ মেলায়।

def josephus_sim(n):
    """People 1..n in a circle; every second person leaves."""
    people = list(range(1, n + 1))
    i, order = 0, []
    while len(people) > 1:
        i = (i + 1) % len(people)            # skip one, remove the next
        order.append(people.pop(i))
    return people[0], order

def josephus_rec(n):                         # J(1)=1, J(2m)=2J(m)-1, J(2m+1)=2J(m)+1
    if n == 1:
        return 1
    j = josephus_rec(n // 2)
    return 2 * j - 1 if n % 2 == 0 else 2 * j + 1

def josephus_bits(n):                        # move the leading 1 to the end
    b = bin(n)[2:]
    return int(b[1:] + b[0], 2)

survivor, order = josephus_sim(10)
print("n = 10 order:", order, "survivor:", survivor)
for n in (10, 41, 100, 1000, 2026):
    m = n.bit_length() - 1                   # n = 2^m + l
    l = n - 2**m
    print(f"n={n:4} sim={josephus_sim(n)[0]:4} rec={josephus_rec(n):4}"
          f" 2l+1={2*l + 1:4}  {bin(n)[2:]} -> {bin(josephus_bits(n))[2:]}")
print("n <= 500 all agree:", all(
    josephus_sim(n)[0] == josephus_rec(n) == josephus_bits(n)
    for n in range(1, 501)))

n = 10 order: [2, 4, 6, 8, 10, 3, 7, 1, 9] survivor: 5
n=  10 sim=   5 rec=   5 2l+1=   5  1010 -> 101
n=  41 sim=  19 rec=  19 2l+1=  19  101001 -> 10011
n= 100 sim=  73 rec=  73 2l+1=  73  1100100 -> 1001001
n=1000 sim= 977 rec= 977 2l+1= 977  1111101000 -> 1111010001
n=2026 sim=2005 rec=2005 2l+1=2005  11111101010 -> 11111010101
n <= 500 all agree: True

৮ · Unrolling-এর কৌশল, algorithm-এর recurrence আর পরীক্ষার অঙ্ক

এই পর্বে বারবার একই তিন ধাপ এসেছে: recurrence বানানো, unrolling করে closed form অনুমান, আর induction দিয়ে প্রমাণ। Unrolling-এর দুটি ছাঁচ মনে রাখার মতো, কারণ পরীক্ষায় বেশিরভাগ order 1-এর recurrence এদের একটিতে পড়ে:

Algorithm-এর recurrence, এক ঝলক। Binary search সাজানো তালিকার মাঝের উপাদান দেখে অর্ধেক ফেলে দেয়। n = 2^k হলে তুলনার একটি সরল মডেল T(1) = 1, T(n) = T(n/2) + 1; unrolling-এ T(n) = log₂ n + 1, যেমন T(1024) = 11. Merge sort তালিকা দুই ভাগ করে, প্রতিটি সাজায়, তারপর জোড়া দেয়। জোড়া দিতে বড়জোর n − 1টি তুলনা লাগে; সহজ রাখতে n ধরলে W(1) = 0, W(n) = 2W(n/2) + n, আর unrolling-এ প্রতিটি স্তরে মোট কাজ n, স্তর log₂ n-টি, তাই W(n) = n log₂ n; যেমন W(1024) = 10240 (scratch-এ যাচাই করা)। n যখন 2-এর ঘাত নয়, তখন ⌊n/2⌋ আর ⌈n/2⌉ আসে, আর কেন 2-এর ঘাত ধরে নেওয়া যায়, master theorem-এর পূর্ণ প্রমাণসহ, তা পর্ব ৪৭ “Divide-and-conquer recurrence আর master theorem-এর গণিত”-এর বিষয়। Algorithm বিশ্লেষণে এদের ব্যবহার দেখতে DSA কোর্সের পর্ব ০৮ আর পর্ব ০৯ পড়ুন।

অঙ্ক ১: Hanoi আর রেখা

(ক) ১০টি চাকতির Hanoi-তে সর্বনিম্ন চাল? (খ) general position-এ ১৫টি রেখা সমতলকে কয় ভাগ করে?

1. (ক) M(10) = 2¹⁰ − 1 = 1023, উপপাদ্য ৪.১ থেকে; এটি শুধু একটি কৌশলের চাল নয়, সর্বনিম্ন।
2. (খ) L(15) = 15 · 16/2 + 1 = 121.

অঙ্ক ২: টালি আর Catalan

(ক) 2 × 12 বোর্ডে domino টালি কয়টি? (খ) recurrence দিয়ে C₅ বের করুন।

1. (ক) t(n) = F_n+1, তাই t(12) = F₁₃ = 233, ব্লকের brute force-এর সঙ্গে মেলে।
2. (খ) C₅ = C₀C₄ + C₁C₃ + C₂C₂ + C₃C₁ + C₄C₀ = 14 + 5 + 4 + 5 + 14 = 42.

অঙ্ক ৩: Josephus

৪১ জনের বৃত্তে প্রতি দ্বিতীয় জন বাদ গেলে কে থাকেন?

1. 41 = 32 + 9, তাই m = 5, l = 9.
2. J(41) = 2 · 9 + 1 = 19. Binary-তে 101001 → 010011 = 19, ব্লকের আউটপুটের সঙ্গে মেলে।

যুক্তির ভুল ধরুন: “ভুল শুরুর মান”

একজন লিখলেন: “দৈর্ঘ্য n-এর ‘00’-হীন bit string-এর সংখ্যা a_n. শেষ bit দেখে a_n = a_n−1 + a_n−2. শুরু a₁ = 1 (string ‘1’) আর a₂ = 2 (‘01’, ‘11’), তাই a₃ = 3, a₄ = 5, a₅ = 8.”

ভুল কোথায়: recurrence ঠিক, initial condition ভুল। দৈর্ঘ্য 1-এ ‘0’-ও বৈধ, কারণ তাতে পরপর দুটি 0 নেই, তাই a₁ = 2; দৈর্ঘ্য 2-এ ‘10’-ও বৈধ, তাই a₂ = 3. সঠিক মান a₃ = 5 (010, 011, 101, 110, 111), a₄ = 8, a₅ = 13. উপপাদ্য ১.২ বলে recurrence একই থাকলেও ভুল শুরু পুরো ধারাকে ভুল করে, আর এখানে প্রতিটি পদ এক ধাপ পেছনের Fibonacci হয়ে গেছে। প্রতিকার: initial condition-গুলোও brute force-এ মিলিয়ে নিন; কৌশল ১.৩-এর ধাপ ২ এ জন্যই।

৯ · AI-এর যুগে — recurrence মডেল যাচাই

“এই সমস্যার recurrence কী?” প্রশ্নে AI সহকারী প্রায় সবসময় একটি সুন্দর উত্তর দেয়। ঝুঁকি হলো উত্তরটি দেখতে ঠিক, কিন্তু একটি ক্ষেত্র বাদ পড়েছে বা শুরুর মান এক ঘর সরে আছে। Recurrence-এ ছোট ভুল প্রতিটি ধাপে বয়ে চলে, তাই শেষ সংখ্যা অনেক দূরে চলে যায়। এই বিষয়ে যে ভুলগুলো নিয়মিত দেখা যায়:

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

• ছোট n-এ brute force গণনার সঙ্গে initial condition আর পরের কয়েকটি মান মিলিয়েছি
• ক্ষেত্রগুলো পরস্পর বিচ্ছিন্ন আর মিলে সব বস্তু ঢাকে কি না দেখেছি
• Order আর initial condition-এর সংখ্যা মেলে কি না দেখেছি
• Closed form-এর induction প্রমাণে ভিত্তি আর ধাপ দুটোই আছে কি না দেখেছি
• “সর্বনিম্ন” বা “সর্বোচ্চ” দাবির সঙ্গে আলাদা সীমার প্রমাণ আছে কি না দেখেছি
• শর্ত (general position, 2-এর ঘাত) ভেঙে একটি counterexample খুঁজে দেখেছি
• সাল আর নাম বিশ্বস্ত উৎসে মিলিয়েছি

Recurrence-এর বড় সুবিধা হলো যাচাই সস্তা: কয়েক লাইনের brute force ছোট n-এ সব বস্তু গুনে ফেলে, আর recurrence-এর প্রথম দশ-বারোটি মান তার সঙ্গে মিললে মডেলে বড় ভুল থাকার সম্ভাবনা কমে যায়। কিন্তু মিল প্রমাণ নয়; প্রমাণ আসে ক্ষেত্রভাগের যুক্তি আর induction থেকে। দুটি একসঙ্গে রাখুন।