ค้นหาเทอมที่ n ของความสัมพันธ์การเกิดซ้ำที่กำหนดใน Python

สมมติว่าเรามีลำดับของตัวเลขที่เรียกว่า bn ซึ่งแสดงโดยใช้ความสัมพันธ์ที่เกิดซ้ำ เช่น b1=1 และ bn+1/bn=2n เราต้องหาค่าของ log2(bn) สำหรับ n ที่กำหนด

ดังนั้น หากอินพุตเท่ากับ 6 เอาต์พุตจะเป็น 5 เนื่องจาก log2(bn) =(n * (n - 1)) / 2 =(6*(6-1))/2 =15

เราสามารถแก้ปัญหานี้ได้โดยแก้ความสัมพันธ์ดังนี้ −

b_n+1 /b_n =2 ⁿ

b_n /b_n-1 =2 ^n-1

…

b₂ /b₁ =2 ¹ , ถ้าเราคูณทั้งหมดข้างต้น เราจะได้

(b_n+1 /b_n ).(b_n /b_n-1 )……(b₂ /b₁ ) =2 ^{n + (n-1)+……….+1}

ดังนั้น b_n+1 /b₁ =2 ^n(n+1)/2

เช่น 1 + 2 + 3 + ………. + (n-1) + n =n(n+1)/2

ดังนั้น b_n+1 =2 ^n(n+1)/2 * b₁; สมมติว่าค่าเริ่มต้น b₁ =1

ดังนั้น b_n+1 =2 ^n(n+1)/2

หลังจากการแทนที่ (n+1) สำหรับ n เราจะได้

b_n =2 ^n(n-1)/2

โดยเอาท่อนซุงทั้งสองข้างเราจะได้

บันทึก₂ (b_n ) =n(n-1)/2

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def add_upto_n(n):
   res = (n * (n - 1)) / 2
   return res
n = 6
print(int(add_upto_n(n)))

อินพุต

6

ผลลัพธ์

15