โจทย์: กำหนดลำดับ bₙ โดย b₁ = 1 และ bₙ₊₁ / bₙ = 2ⁿ หา log₂(bₙ) สำหรับ n ที่กำหนด
การแก้คณิตศาสตร์
bₙ₊₁/bₙ = 2ⁿ
bₙ/bₙ₋₁ = 2ⁿ⁻¹
...
b₂/b₁ = 2¹
คูณทุกสมการ: bₙ₊₁/b₁ = 2^(1+2+...+n) = 2^(n(n+1)/2)
∴ bₙ₊₁ = 2^(n(n+1)/2) (เนื่องจาก b₁ = 1)
แทน n → n-1: bₙ = 2^(n(n-1)/2)
log₂(bₙ) = n(n-1)/2
ตัวอย่างโค้ด
def add_upto_n(n):
res = (n * (n - 1)) // 2
return res
n = 6
print(int(add_upto_n(n))) # 15
ผลลัพธ์
15
สรุป: โจทย์ลดรูปเป็นสูตรปิด (closed-form) n(n-1)/2 คำนวณได้ใน O(1) ไม่ต้องคำนวณลำดับจริง
