Sequence আর summation — closed form আর বিখ্যাত যোগফল

১ · Sequence — নিয়মে বাঁধা তালিকা

বাজারঘরের একটি নতুন শাখা খুলেছে রাজশাহীতে। প্রথম দিন ১২০টি অর্ডার, দ্বিতীয় দিন ১৩৫টি, তৃতীয় দিন ১৫০টি। হিসাবরক্ষক প্রতিদিনের সংখ্যা একটি খাতায় পরপর লিখে রাখেন: 120, 135, 150, 165, … এই তালিকায় ক্রম জরুরি: “তৃতীয় দিনের অর্ডার” একটি নির্দিষ্ট সংখ্যা, আর একই সংখ্যা দুই দিনে আসতেও পারে। গণিতে এমন ক্রমবদ্ধ তালিকাকে বলে sequence (ক্রম)।

অর্থাৎ sequence নতুন কোনো জিনিস নয়, একটি বিশেষ function: ইনপুট হলো অবস্থান (দিন নম্বর), আউটপুট হলো সেই অবস্থানের মান। Function-এর সাধারণ ভাষা (domain, codomain, one-to-one) পর্ব ১৬ “ফাংশন — one-to-one, onto, inverse আর composition”-এ। সসীম sequence a₁, …, a_n-কে প্রোগ্রামিংয়ে বলি list বা array; অক্ষরের সসীম sequence-ই string, যা পর্ব ১২-এ Σ* হিসেবে দেখেছেন।

দুইভাবে নিয়ম দেওয়া — explicit আর recursive

একটি sequence-এর নিয়ম দুইভাবে দেওয়া যায়। Explicit formula-এ n থেকে সরাসরি a_n: যেমন a_n = 120 + 15(n − 1). Recursive সংজ্ঞায় (recurrence) আগের পদ থেকে পরের পদ: a₁ = 120, আর n ≥ 2-এর জন্য a_n = a_n−1 + 15. দ্বিতীয় রূপটি পর্ব ১২-এর recursive definition-এর একটি উদাহরণ; সেখানে দেখেছেন, basis আর নিয়ম মিলে ঠিক একটি sequence দেয়।

দুই রূপের নিজস্ব সুবিধা। Recursive রূপ প্রায়ই সমস্যা থেকে সরাসরি আসে (“প্রতিদিন আগের দিনের চেয়ে ১৫টি বেশি”), কিন্তু a₁₀₀₀ জানতে ৯৯৯ ধাপ লাগে। Explicit রূপে এক ধাপে উত্তর: a₁₀₀₀ = 120 + 15 · 999 = 15105. তাই সাধারণ কাজ হলো recursive রূপ থেকে explicit রূপ খুঁজে বের করা, যাকে recurrence-এর সমাধান বলে। সাধারণ পদ্ধতি পর্ব ৪৪–৪৬-এ আসবে; এই পর্বে সরল ক্ষেত্রগুলো।

বাড়ে না কমে — একঘেয়ে sequence

অনেক প্রমাণে sequence-এর একটি সরল ধর্ম লাগে। {a_n}-কে increasing (বর্ধমান) বলি যদি প্রতিটি n-এর জন্য a_n ≤ a_n+1, আর strictly increasing যদি a_n < a_n+1; decreasing একইভাবে উল্টো দিকে। বাজারঘরের অর্ডার-আইডি 1001, 1002, 1003, … strictly increasing, তাই দুটি আইডি তুলনা করেই বলা যায় কোন অর্ডার আগে এসেছিল। আর “প্রতিদিন পর্যন্ত মোট বিক্রি” সবসময় increasing, কারণ প্রতিদিন একটি অঋণাত্মক সংখ্যা যোগ হয়: S_n+1 − S_n = a_n+1 ≥ 0. এই ছোট পর্যবেক্ষণটি অংশ ৯-এ harmonic number-এর প্রমাণে কাজে লাগবে। একটি sequence bounded (সীমাবদ্ধ) যদি এমন একটি সংখ্যা M থাকে যাতে সব n-এর জন্য |a_n| ≤ M; 1/n সীমাবদ্ধ, 2ⁿ নয়।

কয়েকটি পরিচিত sequence, যাদের নাম পুরো কোর্সে বারবার আসবে:

২ · সমান্তর আর গুণোত্তর ধারা

রাজশাহী শাখার অর্ডার প্রতিদিন একই পরিমাণ (১৫টি) বাড়ছে। এমন sequence-কে বলে arithmetic progression (সমান্তর ধারা, সংক্ষেপে AP). আর বাজারঘরের রেফারেল অফারে প্রতিদিন নতুন গ্রাহক আগের দিনের দ্বিগুণ হলে সংখ্যাগুলো 1, 2, 4, 8, …; প্রতিবার একই গুণক। এটি geometric progression (গুণোত্তর ধারা, GP).

প্রমাণ (ক-এর n-তম পদ, induction): P(n): a_n = a + (n − 1)d.

1. Basis n = 1: সংজ্ঞায় a₁ = a = a + 0 · d.
2. ধরি কোনো k ≥ 1-এর জন্য a_k = a + (k − 1)d (inductive hypothesis).
3. Recursive নিয়মে a_k+1 = a_k + d = a + (k − 1)d + d = a + kd. এটিই P(k + 1). ∎

যোগফলের সূত্রটি পরের দুই অংশে Gauss-এর জোড়ার কৌশলে প্রমাণ হবে, আর GP-র যোগফলের induction-প্রমাণ পর্ব ১০-এ আছে; অংশ ৬-এ একই সূত্র একটি নতুন কৌশলে (perturbation) বের করব।

পরীক্ষার ধাঁচের হিসাব ১: রাজশাহী শাখার প্রথম ৩০ দিনের মোট অর্ডার কত? a = 120, d = 15, n = 30. শেষ পদ a₃₀ = 120 + 29 · 15 = 555. মোট S₃₀ = 30(120 + 555)/2 = 15 · 675 = 10125টি অর্ডার।

পরীক্ষার ধাঁচের হিসাব ২: একটি AP-র ৫ম পদ 23 আর ১২তম পদ 51. প্রথম ২০ পদের যোগফল কত? a + 4d = 23 আর a + 11d = 51; বিয়োগ করে 7d = 28, তাই d = 4 আর a = 7. S₂₀ = 20(2 · 7 + 19 · 4)/2 = 10 · 90 = 900.

পরীক্ষার ধাঁচের হিসাব ৩ (GP): বাজারঘরের রেফারেল অফারের শুরুর দিনে (দিন 0) ৫ জন নতুন গ্রাহক এলেন, আর প্রতিদিন নতুন গ্রাহক আগের দিনের তিন গুণ। (ক) দিন 0 থেকে দিন 7, এই আট দিনে মোট কতজন? (খ) কততম দিনের শেষে মোট সংখ্যা প্রথম এক লাখ ছাড়াবে? (ক) a = 5, r = 3, ঘাত 0 থেকে 7: 5(3⁸ − 1)/(3 − 1) = 5 · 6560/2 = 16400 জন। (খ) প্রথম n দিনে (দিন 0 থেকে n − 1) মোট 5(3ⁿ − 1)/2. এটি 100000-এর বেশি হতে হলে 3ⁿ > 40001. 3⁹ = 19683 যথেষ্ট নয়, 3¹⁰ = 59049 যথেষ্ট; তাই n = 10, অর্থাৎ দিন 9-এর শেষে মোট 147620 জন (দিন 8-এর শেষে মোট ছিল 49205 জন)। বাস্তবে এমন বৃদ্ধি বেশিদিন চলে না, কারণ গ্রাহকের সংখ্যা সসীম; গুণোত্তর ধারা শুধু শুরুর দিকের ভালো মডেল।

৩ · কয়েকটি পদ দেখে নিয়ম অনুমান — আর তার সীমা

চাকরির aptitude পরীক্ষায় প্রায়ই প্রশ্ন আসে: “ধারার পরের সংখ্যাটি কত?” গণিতের দৃষ্টিতে এমন প্রশ্নের কঠোর উত্তর হলো: যেকোনো সংখ্যা হতে পারে। সসীম কয়েকটি পদ অসীম sequence-কে নির্দিষ্ট করে না। তবু অনুমান করার ভালো কৌশল আছে, আর সেগুলো প্রমাণের পথ দেখায়।

Difference table

একটি sequence-এর পাশাপাশি পদের পার্থক্য নিলে নতুন একটি sequence পাই: Δa_n = a_n+1 − a_n. একে বলে forward difference. পার্থক্যের পার্থক্য নিতে থাকলে একটি difference table তৈরি হয়। একটি গুরুত্বপূর্ণ তথ্য: a_n যদি n-এর d-মাত্রার polynomial হয়, তাহলে d-তম পার্থক্যের সারি ধ্রুবক, আর তার পরের সারি শূন্য। যেমন a_n = n² হলে Δa_n = (n + 1)² − n² = 2n + 1, যা মাত্রা 1-এর; তার পার্থক্য 2, ধ্রুবক। বাজারঘরের নতুন শাখার প্রথম পাঁচ দিনের মোট অর্ডার (হাজারে) 3, 8, 15, 24, 35 হলে নিচের ব্লক টেবিল বানিয়ে পরের মান অনুমান করে, তারপর একটি সতর্কতার উদাহরণ দেখায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from math import comb

def diff_table(seq):                 # rows of successive differences
    rows = [list(seq)]
    while len(rows[-1]) > 1:
        r = rows[-1]
        rows.append([r[i + 1] - r[i] for i in range(len(r) - 1)])
    return rows

def next_term(seq):                  # assume the last row stays constant
    return sum(row[-1] for row in diff_table(seq))

orders = [3, 8, 15, 24, 35]          # total orders after day 1..5
for row in diff_table(orders):
    print(row)
print("guess for day 6:", next_term(orders))

data = [1, 2, 4, 8, 16]
print()
for row in diff_table(data):
    print(row)
print("difference-table guess:", next_term(data))

doubling = [2 ** (n - 1) for n in range(1, 8)]
circle = [comb(n, 4) + comb(n, 2) + 1 for n in range(1, 8)]
print("rule 2^(n-1):        ", doubling)
print("rule C(n,4)+C(n,2)+1:", circle)

[3, 8, 15, 24, 35]
[5, 7, 9, 11]
[2, 2, 2]
[0, 0]
[0]
guess for day 6: 48

[1, 2, 4, 8, 16]
[1, 2, 4, 8]
[1, 2, 4]
[1, 2]
[1]
difference-table guess: 31
rule 2^(n-1):         [1, 2, 4, 8, 16, 32, 64]
rule C(n,4)+C(n,2)+1: [1, 2, 4, 8, 16, 31, 57]

দ্বিতীয় নিয়মটি বানানো উদাহরণ নয়। একটি বৃত্তের ওপর n টি বিন্দু নিয়ে প্রতি জোড়া বিন্দু সরলরেখায় যুক্ত করুন, এমনভাবে যাতে তিনটি রেখা ভেতরের একই বিন্দুতে না মেলে। বৃত্তের ভেতরটা কয়টি অংশে ভাগ হয়? n = 1 থেকে 5-এ উত্তর 1, 2, 4, 8, 16, কিন্তু n = 6-এ 31. সূত্রটি C(n, 4) + C(n, 2) + 1; এটি কেন, তা গণনার মডিউলে (পর্ব ৩৪ “Binomial coefficient, Pascal-এর ত্রিভুজ আর combinatorial identity”-এর ভাষায়) বোঝা যায়। শিক্ষা একটাই: কয়েকটি মিল প্রমাণ নয়।

প্রমাণ:

1. ধরি q হলো মাত্রা ≤ m − 1-এর একটি polynomial যা প্রথম m মান মেলায় (এমন q সবসময় আছে: Lagrange-এর interpolation সূত্র, যা প্রতিটি বিন্দুর জন্য একটি পদ দিয়ে তৈরি; এখানে আমরা এর অস্তিত্ব মেনে নিচ্ছি)।
2. w(x) = (x − 1)(x − 2)…(x − m) নিন। x = 1, …, m-এ w(x) = 0, আর w(m + 1) = m! ≠ 0.
3. p(x) = q(x) + t · w(x) নিন, যেখানে t = (c − q(m + 1))/m!.
4. x = 1, …, m-এ p(x) = q(x) + 0 = b_x, আর p(m + 1) = q(m + 1) + (c − q(m + 1)) = c. মাত্রা ≤ m. ∎

তাই “1, 2, 4, 8, 16-এর পরে কী?” প্রশ্নে 32-ও ঠিক, 31-ও ঠিক, এমনকি 2026-ও ঠিক, যদি নিয়মটি বলে দেওয়া হয়। পরীক্ষায় এই প্রশ্নের আসল অর্থ: “সবচেয়ে সরল স্বাভাবিক নিয়ম কোনটি?” গণিতে কাজের ধারা অন্য: অনুমান করুন, অনেক পদে যন্ত্রে মিলিয়ে নিন, তারপর প্রমাণ করুন।

৪ · Σ চিহ্ন — যোগফলের সংক্ষিপ্ত লিখন আর তার নিয়ম

“1 + 2 + … + n” লেখায় “…” অংশটি পাঠকের অনুমানের ওপর ছেড়ে দেয়। নিখুঁত লিখনের জন্য গ্রিক অক্ষর সিগমা দিয়ে summation লেখা হয়:

∑_k=mⁿ a_k = a_m + a_m+1 + … + a_n

এখানে k হলো index of summation (যোগের সূচক), m নিচের সীমা আর n ওপরের সীমা। পদসংখ্যা n − m + 1. সূচকের নাম নিজে গুরুত্বহীন: ∑_k=1⁵ k² আর ∑_j=1⁵ j² একই সংখ্যা, 55. প্রোগ্রামারের চোখে ∑ একটি লুপ, আর k লুপের variable:

total = 0
for k in range(m, n + 1):     # k = m, m+1, ..., n
    total += a(k)

সংজ্ঞাটিও recursive: n < m হলে ∑_k=mⁿ a_k = 0 (empty sum, কোনো পদ নেই, যেমন লুপ একবারও না চললে total = 0); আর n ≥ m হলে ∑_k=mⁿ a_k = (∑_k=mⁿ⁻¹ a_k) + a_n. এই সংজ্ঞার কারণেই ∑-এর প্রতিটি নিয়ম n-এর ওপর induction দিয়ে প্রমাণ করা যায়।

প্রমাণ (১, n-এর ওপর induction, m স্থির):

1. Basis n = m − 1: দুই পাশেই empty sum, 0 = c · 0 + 0.
2. ধরি কোনো n ≥ m − 1-এর জন্য (১) সত্য।
3. সংজ্ঞায় ∑_k=mⁿ⁺¹ (c·a_k + b_k) = ∑_k=mⁿ (c·a_k + b_k) + c·a_n+1 + b_n+1.
4. Hypothesis বসিয়ে আর পদ সাজিয়ে: = c(∑_k=mⁿ a_k + a_n+1) + (∑_k=mⁿ b_k + b_n+1) = c·∑_k=mⁿ⁺¹ a_k + ∑_k=mⁿ⁺¹ b_k. ∎

(৪)-এর যুক্তি সরাসরি: j = k + s বসালে k = m হলে j = m + s, k = n হলে j = n + s, আর a_k = a_j−s. দুই পাশে হুবহু একই পদ, একই ক্রমে। (২) আর (৩)-ও একইভাবে induction-এ আসে; সেগুলো নিজে লিখে দেখুন।

উদাহরণ: ∑_k=1²⁰ (3k + 2) = 3∑_k=1²⁰ k + ∑_k=1²⁰ 2 = 3 · 210 + 20 · 2 = 670. আর index shift দিয়ে ∑_k=0ⁿ⁻¹ (k + 1)² = ∑_j=1ⁿ j²: j = k + 1 বসালে সীমা 0..n−1 থেকে 1..n হয়।

মাঝখান থেকে শুরু হওয়া যোগফল: ∑_k=10²⁰ k² কত? ভাঙার নিয়মে ∑_k=1²⁰ k² = ∑_k=1⁹ k² + ∑_k=10²⁰ k², তাই চাওয়া যোগফল = 2870 − 285 = 2585 (দুটি মান অংশ ৬-এর ∑k²-এর সূত্র থেকে)। পরীক্ষায় এই কৌশল খুব কাজের: প্রায় সব closed form 1 থেকে শুরু হয়, তাই অন্য নিচের সীমা থাকলে “পুরোটা বিয়োগ শুরুর অংশ” লিখুন। সতর্ক থাকুন, বাদ দিতে হবে 1 থেকে 9, 10 পর্যন্ত নয়; নইলে 10²-ও বাদ পড়ে যায়।

অসীম যোগফল ∑_k=0^∞ a_k মানে আংশিক যোগফল (partial sum) S_n = ∑_k=0ⁿ a_k-এর সীমা, যদি সীমা থাকে। যেমন |r| < 1 হলে rⁿ⁺¹ → 0, তাই ∑_k=0^∞ r^k = 1/(1 − r); 1 + 1/2 + 1/4 + … = 2. সীমা থাকার প্রশ্নটি calculus-এর বিষয়; এই কোর্সে বেশির ভাগ যোগফল সসীম, আর অসীম যোগফল এলে আমরা তা স্পষ্ট বলব।

৫ · Gauss-এর জোড়া — ১ থেকে n পর্যন্ত যোগফল

কৌশলটি হলো যোগফলটিকে দুইবার লেখা, একবার সামনে থেকে, একবার পেছন থেকে, তারপর কলাম ধরে যোগ করা। n = 6 দিয়ে দেখুন; “পরে” চাপুন:

1 S = 1 + 2 + 3 + 4 + 5 + 62 S = 6 + 5 + 4 + 3 + 2 + 132S = 7 + 7 + 7 + 7 + 7 + 742S = 6 · 7 = 4252S = n(n + 1)

প্রমাণ (∑-এর নিয়ম দিয়ে Gauss-এর যুক্তি):

1. S = ∑_k=1ⁿ k লিখি।
2. j = n + 1 − k বসাই। k যখন 1 থেকে n, j তখন n থেকে 1, প্রতিটি মান একবার করে; তাই S = ∑_j=1ⁿ (n + 1 − j). (এটি index-এর উল্টো ক্রম; যোগের বিনিময় ধর্মে মান বদলায় না।)
3. দুই রূপ যোগ করে, linearity দিয়ে: 2S = ∑_k=1ⁿ (k + (n + 1 − k)) = ∑_k=1ⁿ (n + 1).
4. ধ্রুবকের যোগের নিয়মে 2S = n(n + 1), তাই S = n(n + 1)/2. ∎

এই যোগফলগুলোকে বলে ত্রিভুজ সংখ্যা T_n, কারণ বিন্দু দিয়ে সাজালে ত্রিভুজ হয়। নিচের ছবিতে Gauss-এর যুক্তিটি জ্যামিতিতে: দুটি একই রকম সিঁড়ি মিলে একটি আয়তক্ষেত্র।

AP-র যোগফলের প্রমাণ (উপপাদ্য ২.১ক): প্রথম n পদ a + kd, k = 0, …, n − 1. Linearity আর ধ্রুবকের নিয়মে S_n = ∑_k=0ⁿ⁻¹ (a + kd) = na + d∑_k=0ⁿ⁻¹ k = na + d(n − 1)n/2 = n(2a + (n − 1)d)/2. শেষ ধাপে উপপাদ্য ৫.১ ব্যবহার হয়েছে n − 1 দিয়ে (k = 0-এর পদ শূন্য)। ∎ একই জোড়ার যুক্তি যেকোনো AP-তে খাটে, কারণ প্রথম আর শেষ পদের যোগফল, দ্বিতীয় আর শেষের আগের পদের যোগফল, এভাবে সব জোড়ার যোগফল সমান।

৬ · Telescoping — পাশাপাশি পদ কাটাকাটি

পুরোনো দূরবীন (telescope) ভাঁজ করলে সব খণ্ড একটির ভেতরে আরেকটি ঢুকে যায়, বাইরে থাকে শুধু প্রথম আর শেষ খণ্ড। কিছু যোগফলও এভাবে গুটিয়ে যায়।

প্রমাণ (n-এর ওপর induction):

1. Basis n = 0: বাঁ পাশ empty sum 0, ডান পাশ a₀ − a₀ = 0.
2. ধরি কোনো n ≥ 0-এর জন্য সমতা সত্য।
3. ∑_k=0ⁿ (a_k+1 − a_k) = (a_n − a₀) + (a_n+1 − a_n) = a_n+1 − a₀, ∑-এর সংজ্ঞা আর hypothesis থেকে। ∎

বিখ্যাত উদাহরণ: 1/(k(k + 1)) = 1/k − 1/(k + 1), যা হর মিলিয়ে সহজে মেলে। তাই

∑_k=1ⁿ 1/(k(k + 1)) = (1 − 1/2) + (1/2 − 1/3) + … + (1/n − 1/(n + 1)) = 1 − 1/(n + 1) = n/(n + 1).

খেয়াল করুন, এটি “−” চিহ্নসহ উপপাদ্য ৬.১: a_k = 1/k নিলে প্রতিটি পদ −(a_k+1 − a_k). n বাড়লে যোগফল 1-এর দিকে যায়, কিন্তু কখনো 1 ছোঁয় না।

Telescoping দিয়ে ∑k² আবিষ্কার

∑k²-এর সূত্র অনুমান না করে বের করা যায়। কৌশল: এমন একটি পার্থক্য নিন যার ভেতরে k² আসে। (k + 1)³ − k³ = 3k² + 3k + 1. এবার k = 1 থেকে n পর্যন্ত যোগ করুন।

1. বাঁ পাশ telescoping: ∑_k=1ⁿ ((k + 1)³ − k³) = (n + 1)³ − 1.
2. ডান পাশ linearity দিয়ে: 3∑k² + 3∑k + n = 3Q + 3n(n + 1)/2 + n, যেখানে Q = ∑_k=1ⁿ k².
3. সমান করে: 3Q = (n + 1)³ − 1 − n − 3n(n + 1)/2 = (n + 1)³ − (n + 1) − 3n(n + 1)/2.
4. (n + 1) সাধারণ উৎপাদক: 3Q = (n + 1)[(n + 1)² − 1 − 3n/2] = (n + 1)(n² + 2n − 3n/2) = (n + 1) · n(2n + 1)/2.
5. তাই Q = n(n + 1)(2n + 1)/6. ∎

যাচাই: n = 3-এ 1 + 4 + 9 = 14, আর সূত্রে 3 · 4 · 7/6 = 14. একই কৌশলে (k + 1)⁴ − k⁴ থেকে ∑k³, আর সাধারণভাবে ∑k^p-এর সূত্র ধাপে ধাপে পাওয়া যায়; প্রতিটি ধাপে আগের সব সূত্র লাগে, ঠিক strong induction-এর মতো।

প্রমাণ (induction):

1. Basis n = 1: 1³ = 1 = (1 · 2/2)².
2. ধরি কোনো k ≥ 1-এর জন্য ∑_i=1^k i³ = k²(k + 1)²/4.
3. তাহলে ∑_i=1^k+1 i³ = k²(k + 1)²/4 + (k + 1)³ = (k + 1)²[k² + 4(k + 1)]/4.
4. k² + 4k + 4 = (k + 2)², তাই যোগফল (k + 1)²(k + 2)²/4 = ((k + 1)(k + 2)/2)². এটিই n = k + 1-এর দাবি। ∎

ফলটি চমকপ্রদ: প্রথম n টি ঘনের যোগফল প্রথম n টি সংখ্যার যোগফলের বর্গ। 1 + 8 + 27 + 64 = 100 = 10². ইতিহাসে এটি প্রায়ই খ্রিস্টীয় প্রথম-দ্বিতীয় শতকের Nicomachus-এর নামে বলা হয়; ভারতে Aryabhata (৪৯৯ খ্রিস্টাব্দের Aryabhatiya) বর্গ আর ঘনের যোগফলের নিয়ম দিয়েছিলেন বলে ইতিহাসবিদরা উল্লেখ করেন।

৭ · Perturbation — যোগফলকে একটু নাড়িয়ে সমীকরণ

Gauss-এর জোড়া AP-তে কাজ করে, কিন্তু GP-তে করে না। GP-র জন্য অন্য কৌশল, যার নাম perturbation method: একই যোগফলকে দুই ভাবে লিখে একটি সমীকরণ পাওয়া, যার সমাধানই closed form. প্রথমে geometric series G_n = ∑_k=0ⁿ r^k.

1. শেষ পদ আলাদা করে: G_n+1 = G_n + rⁿ⁺¹.
2. প্রথম পদ আলাদা করে, তারপর index shift: G_n+1 = 1 + ∑_k=1ⁿ⁺¹ r^k = 1 + r∑_k=0ⁿ r^k = 1 + rG_n.
3. দুটি সমান: G_n + rⁿ⁺¹ = 1 + rG_n, তাই (r − 1)G_n = rⁿ⁺¹ − 1.
4. r ≠ 1 হলে ভাগ করা যায়: G_n = (rⁿ⁺¹ − 1)/(r − 1). ∎

ধাপ ৪-এ “r ≠ 1” শর্তটি অলংকার নয়: শূন্য দিয়ে ভাগ বৈধ নয়। এই একই ধারণা জটিল যোগফলেও খাটে, যেখানে অনুমান করা কঠিন। যেমন ∑k·2^k: height h-এর একটি perfect binary tree-এ গভীরতা k-তে 2^kটি node, তাই সব node-এর গভীরতার মোট ∑_k=0^h k·2^k. এই ধরনের যোগফল (আর তার আত্মীয় ∑k/2^k) tree-ভিত্তিক algorithm-এর বিশ্লেষণে আসে। n = 3 পাশে রেখে ধাপগুলো দেখুন:

1S  = Σ k·2^k, k=0..n2S′ = S + (n+1)·2^(n+1)3S′ = Σ (k+1)·2^(k+1)4S′ = 2S + 2^(n+2) − 25S  = (n−1)·2^(n+1) + 2

এবার এ পর্যন্ত পাওয়া সব closed form একসঙ্গে যন্ত্রে মিলিয়ে নিই, আর একটি ভুয়া সূত্রও রাখি। সেটি ∑k²-এর প্রথম তিনটি মান (1, 5, 14) হুবহু মেলায়। শেষ অংশে Python-এর Fraction দিয়ে (নির্ভুল ভগ্নাংশ, float-এর গোলমাল নেই) telescoping যোগফল দেখা হয়েছে:

from fractions import Fraction

claims = {                           # term a(k), claimed closed form S(n)
    "k":          (lambda k: k,        lambda n: n * (n + 1) // 2),
    "k^2":        (lambda k: k * k,    lambda n: n * (n + 1) * (2 * n + 1) // 6),
    "k^3":        (lambda k: k ** 3,   lambda n: (n * (n + 1) // 2) ** 2),
    "3^k":        (lambda k: 3 ** k,   lambda n: (3 ** (n + 1) - 3) // 2),
    "k*2^k":      (lambda k: k * 2**k, lambda n: (n - 1) * 2 ** (n + 1) + 2),
    "k^2 (fake)": (lambda k: k * k,    lambda n: (5 * n * n - 7 * n + 4) // 2),
}
for name, (term, S) in claims.items():
    total, bad = 0, None
    for n in range(1, 101):
        total += term(n)             # running sum a(1) + ... + a(n)
        if total != S(n) and bad is None:
            bad = n
    verdict = "holds for n = 1..100" if bad is None else f"fails first at n = {bad}"
    print(f"sum of {name:11} {verdict}")

print()
s = Fraction(0)
for k in range(1, 7):                # 1/(k(k+1)) = 1/k - 1/(k+1)
    s += Fraction(1, k * (k + 1))
    print(k, s, "  1 - 1/(n+1) =", 1 - Fraction(1, k + 1))

sum of k           holds for n = 1..100
sum of k^2         holds for n = 1..100
sum of k^3         holds for n = 1..100
sum of 3^k         holds for n = 1..100
sum of k*2^k       holds for n = 1..100
sum of k^2 (fake)  fails first at n = 4

1 1/2   1 - 1/(n+1) = 1/2
2 2/3   1 - 1/(n+1) = 2/3
3 3/4   1 - 1/(n+1) = 3/4
4 4/5   1 - 1/(n+1) = 4/5
5 5/6   1 - 1/(n+1) = 5/6
6 6/7   1 - 1/(n+1) = 6/7

৮ · Double sum, ∏ চিহ্ন আর লুপের কাজ গোনা

বাজারঘরের ৩টি গুদাম আর ৪টি জেলা। গুদাম i থেকে জেলা j-তে দৈনিক চালান a_ij হলে মোট চালান একটি double sum: ∑_i=1³ ∑_j=1⁴ a_ij. ভেতরের যোগফল আগে (একটি গুদামের সব জেলা), তারপর বাইরের। প্রোগ্রামে এটি দুই স্তরের লুপ। আয়তাকার পরিসরে যোগের ক্রম বদলালে মান বদলায় না (সসীম যোগফলে পদগুলো যেকোনো ক্রমে যোগ করা যায়), আর পদটি i-এর অংশ আর j-এর অংশের গুণফল হলে যোগফল আলাদা হয়ে যায়: ∑_i=1³ ∑_j=1⁴ ij = (∑i)(∑j) = 6 · 10 = 60.

আসল মজা ত্রিভুজাকার পরিসরে, যেখানে ভেতরের সীমা বাইরের সূচকের ওপর নির্ভর করে। ∑_i=1ⁿ ∑_j=1ⁱ a_ij মানে 1 ≤ j ≤ i ≤ n শর্ত মানা সব জোড়ার ওপর যোগ।

প্রমাণ:

1. বাঁ পাশে প্রতিটি পদ a_ij আসে ঠিক তখন, যখন 1 ≤ i ≤ n আর 1 ≤ j ≤ i, অর্থাৎ যখন 1 ≤ j ≤ i ≤ n; প্রতিটি এমন জোড়া একবারই আসে।
2. ডান পাশে a_ij আসে ঠিক তখন, যখন 1 ≤ j ≤ n আর j ≤ i ≤ n, অর্থাৎ আবার 1 ≤ j ≤ i ≤ n, প্রতিটি জোড়া একবার।
3. দুই পাশে একই সসীম পদ-সংগ্রহ, শুধু ক্রম আলাদা; যোগের বিনিময় আর সংযোগ ধর্মে মান সমান। ∎

কৌশলটি মনে রাখার সহজ উপায়: সূচকের শর্তগুলো একটি অসমতা-শিকলে লিখুন (এখানে 1 ≤ j ≤ i ≤ n), তারপর যে সূচক বাইরে রাখতে চান তার সীমা শিকল থেকে পড়ে নিন। পরের অংশে এই কৌশলে harmonic number-এর একটি যোগফল বের হবে।

∏ চিহ্ন আর factorial

যোগের জন্য যেমন ∑, গুণের জন্য তেমন ∏ (বড় হাতের গ্রিক পাই): ∏_k=mⁿ a_k = a_m · a_m+1 · … · a_n. এই product notation-এর সংজ্ঞাও recursive, কিন্তু কোনো পদ না থাকলে মান 1 (empty product), কারণ গুণে 1 কিছু বদলায় না, যেমন যোগে 0. তাই n! = ∏_k=1ⁿ k, আর 0! = 1 কোনো বিশেষ ছাড় নয়, empty product-এর স্বাভাবিক মান। দুই চিহ্নের সম্পর্ক logarithm দিয়ে: সব a_k > 0 হলে log ∏a_k = ∑ log a_k. Machine learning-এ অনেক ছোট সম্ভাবনার গুণফলের বদলে log-এর যোগফল নেওয়া হয় ঠিক এই কারণে।

Product-ও telescoping হয়: ∏_k=1ⁿ (1 + 1/k) = ∏_k=1ⁿ (k + 1)/k = (2/1)(3/2)…((n + 1)/n) = n + 1. প্রতিটি লব পরের হরের সঙ্গে কাটে।

লুপ গোনা মানে যোগফল

একটি algorithm কতক্ষণ চলে, তার প্রথম ধাপ হলো মূল কাজটি কতবার হয় তা গোনা। নিয়ম সরল: একটি লুপের মোট কাজ = প্রতিটি পুনরাবৃত্তির কাজের যোগফল। বাজারঘরের n জন গ্রাহকের তালিকায় ডুপ্লিকেট খুঁজতে প্রতিটি জোড়া একবার তুলনা করা হয়। n = 5 নিয়ে ভেতরের লুপ কতবার চলে, দেখুন:

1c = 02for i in range(5):3  for j in range(i+1, 5):4    c += 1   # pair i, j5print(c)

এই n(n − 1)/2-ই n টি জিনিস থেকে ২টি বাছার উপায়ের সংখ্যা C(n, 2); কেন, তা পর্ব ৩৩ “Permutation আর combination”-এ। Bubble sort-এর তুলনার সংখ্যাও এই যোগফল (DSA কোর্সের পর্ব ২০)। যোগফল থেকে বৃদ্ধির হার: n(n − 1)/2 = Θ(n²); Big-O, Ω আর Θ-র সংজ্ঞা DSA কোর্সের পর্ব ৪-এ, আর এ ধরনের যোগফলের তালিকা পর্ব ৬-এ। ভেতরের কাজ নিজেই i-এর ওপর নির্ভর করলে একই ধারা: যেমন বাইরের লুপের i-তম ধাপে ভেতরে i² কাজ হলে মোট ∑_i=1ⁿ i² = n(n + 1)(2n + 1)/6 = Θ(n³); n = 100-এ 338350. সাধারণ নিয়ম হলো, প্রতিটি স্তরের লুপ একটি ∑, আর সবচেয়ে ভেতরের কাজ যোগফলের পদ। নিচের ব্লক তিন রকম লুপ গুনে সূত্রের সঙ্গে মেলায়; তৃতীয়টিতে ভেতরের লুপ i ধাপে লাফায়, যা sieve ধরনের algorithm-এ দেখা যায়।

from math import comb, log

def pairs(n):                        # compare every pair of customer ids
    c = 0
    for i in range(n):
        for j in range(i + 1, n):
            c += 1
    return c

def triples(n):                      # every set of 3 customers
    c = 0
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                c += 1
    return c

def multiples(n):                    # inner loop jumps by i
    c = 0
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            c += 1
    return c

for n in (10, 100, 1000):
    H = sum(1 / k for k in range(1, n + 1))
    print(f"n={n}: pairs {pairs(n)} = n(n-1)/2 = {n * (n - 1) // 2}")
    if n <= 100:
        print(f"      triples {triples(n)} = C(n,3) = {comb(n, 3)}")
    print(f"      multiples {multiples(n)}, n*H_n = {n * H:.1f},"
          f" n ln n = {n * log(n):.1f}")

n=10: pairs 45 = n(n-1)/2 = 45
      triples 120 = C(n,3) = 120
      multiples 27, n*H_n = 29.3, n ln n = 23.0
n=100: pairs 4950 = n(n-1)/2 = 4950
      triples 161700 = C(n,3) = 161700
      multiples 482, n*H_n = 518.7, n ln n = 460.5
n=1000: pairs 499500 = n(n-1)/2 = 499500
      multiples 7069, n*H_n = 7485.5, n ln n = 6907.8

৯ · Harmonic number — অসীমে যায়, কিন্তু খুব ধীরে

Harmonic number H_n = ∑_k=1ⁿ 1/k = 1 + 1/2 + 1/3 + … + 1/n. যেমন H₅ = 137/60 ≈ 2.283. পদগুলো ক্রমে শূন্যের দিকে যায়, তাই মনে হতে পারে যোগফল কোনো সীমায় থামবে। থামে না: অসীম harmonic series ∑1/k যেকোনো সংখ্যাকে ছাড়িয়ে যায়। নিচের প্রমাণে কোনো calculus লাগে না।

প্রমাণ (m-এর ওপর induction):

1. Basis m = 0: H₁ = 1 ≥ 1 + 0.
2. ধরি কোনো m ≥ 0-এর জন্য H_2^m ≥ 1 + m/2.
3. ∑-এর ভাঙার নিয়মে H_2^m+1 = H_2^m + ∑_k=2^m+1^2m+1 1/k.
4. দ্বিতীয় যোগফলে পদ 2^m+1 − 2^m = 2^mটি, আর প্রতিটি পদ ≥ সবচেয়ে ছোট পদ 1/2^m+1. তাই সেটি ≥ 2^m/2^m+1 = 1/2.
5. Hypothesis মিলিয়ে H_2^m+1 ≥ 1 + m/2 + 1/2 = 1 + (m + 1)/2. ∎
6. যেকোনো সংখ্যা M-এর জন্য m > 2M নিলে H_2^m > M; আর H_n n-এর সঙ্গে বাড়ে, তাই এর কোনো ঊর্ধ্বসীমা নেই।

যুক্তিটি চতুর্দশ শতকের ফরাসি পণ্ডিত Nicole Oresme-এর বলে প্রচলিত (আনুমানিক ১৩৫০ সালের দিকে)। কিন্তু বৃদ্ধি অত্যন্ত ধীর। কতটা ধীর, তা সামান্য calculus দিয়ে নিখুঁত করা যায়: y = 1/x বক্ররেখার নিচের ক্ষেত্রফলের সঙ্গে আয়তক্ষেত্রের তুলনা।

প্রমাণের রূপরেখা: 1/x ক্রমহ্রাসমান, তাই k ≤ x ≤ k + 1-এ 1/(k + 1) ≤ 1/x ≤ 1/k, আর সমতা শুধু প্রান্তে। (১) ∫_k^k+1 dx/x < 1/k; k = 1..n যোগ করে ln(n + 1) < H_n (ছবি ৯.১)। (২) ∫_k−1^k dx/x > 1/k (k ≥ 2): আয়তক্ষেত্রগুলো এক ঘর বাঁয়ে সরালে বক্ররেখার নিচে চলে যায়; k = 2..n যোগ করে H_n − 1 ≤ ln n, n = 1-এ সমতা। এখানে ∫dx/x = ln x, calculus-এর তথ্য, আমরা মেনে নিচ্ছি। ∎

দুই সীমার পার্থক্য 1-এর কম, তাই H_n = ln n + O(1), অর্থাৎ Θ(log n). আরও সূক্ষ্মভাবে H_n − ln n একটি ধ্রুবকের দিকে যায়, যাকে বলে Euler–Mascheroni constant γ ≈ 0.5772. এর প্রমাণ (পার্থক্যটি ক্রমহ্রাসমান আর নিচে সীমাবদ্ধ) আমরা বাদ রাখছি। নিচের ব্লক সংখ্যাগুলো দেখায়:

from fractions import Fraction
from math import log

print("H_5 exactly:", sum(Fraction(1, k) for k in range(1, 6)))
print(f"{'n':>8} {'H_n':>8} {'ln n':>8} {'H_n - ln n':>11}  ln(n+1) < H_n <= 1+ln n")
show = {1, 2, 5, 10, 100, 1000, 10**4, 10**5, 10**6}
H, first_over_10 = 0.0, None
for n in range(1, 10**6 + 1):
    H += 1 / n
    if H > 10 and first_over_10 is None:
        first_over_10 = n
    if n in show:
        ok = log(n + 1) < H <= 1 + log(n)
        print(f"{n:>8} {H:8.4f} {log(n):8.4f} {H - log(n):11.6f}  {ok}")
print("Euler's constant gamma ~ 0.577216")
print("first n with H_n > 10:", first_over_10)

H_5 exactly: 137/60
       n      H_n     ln n  H_n - ln n  ln(n+1) < H_n <= 1+ln n
       1   1.0000   0.0000    1.000000  True
       2   1.5000   0.6931    0.806853  True
       5   2.2833   1.6094    0.673895  True
      10   2.9290   2.3026    0.626383  True
     100   5.1874   4.6052    0.582207  True
    1000   7.4855   6.9078    0.577716  True
   10000   9.7876   9.2103    0.577266  True
  100000  12.0901  11.5129    0.577221  True
 1000000  14.3927  13.8155    0.577216  True
Euler's constant gamma ~ 0.577216
first n with H_n > 10: 12367

পরীক্ষার ধাঁচের হিসাব: ∑_i=1ⁿ H_i-এর closed form বের করুন। H_i = ∑_j=1ⁱ 1/j, তাই এটি ত্রিভুজাকার double sum. উপপাদ্য ৮.১ দিয়ে ক্রম বদলে: ∑_j=1ⁿ ∑_i=jⁿ 1/j = ∑_j=1ⁿ (n − j + 1)/j = (n + 1)∑_j=1ⁿ 1/j − ∑_j=1ⁿ 1 = (n + 1)H_n − n. যাচাই n = 3: H₁ + H₂ + H₃ = 1 + 3/2 + 11/6 = 13/3, আর 4 · 11/6 − 3 = 22/3 − 3 = 13/3. ✓

Harmonic number কম্পিউটার বিজ্ঞানে বারবার আসে: quicksort-এর গড় তুলনা-সংখ্যার হিসাবে, ওপরের sieve-ধরনের লুপে, আর “কুপন সংগ্রহ” সমস্যায়। বাজারঘর প্রতিটি অর্ডারের সঙ্গে n রকম স্টিকারের একটি এলোমেলোভাবে দিলে সব রকম পেতে গড়ে n·H_nটি অর্ডার লাগে; এর প্রমাণ পর্ব ৪০ “Random variable আর প্রত্যাশা”-য়।

১০ · AI-এর যুগে — AI-এর দেওয়া closed form আর লুপ-হিসাব যাচাই

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

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

• যোগফলের নিচের আর ওপরের সীমা, আর পদসংখ্যা, নিজে গুনে মিলিয়েছি
• n = 0, 1, 2-এ সূত্র আর সরাসরি যোগফল হাতে মিলিয়েছি
• Python-এ অনেক n-এ (নির্ভুল int বা Fraction দিয়ে) তুলনা করেছি
• প্রমাণে basis আছে, আর প্রতিটি ধাপের কারণ লেখা আছে
• প্রতিটি ভাগে হর অশূন্য, আর অসীম যোগফলে সীমার শর্ত বলা আছে
• লুপের হিসাবে ছোট n-এ counter দিয়ে আসল পুনরাবৃত্তি গুনেছি