Tower of hanoi

[GranDAnGlE]

รบกวน ช่วยทีครับ
คือผมพิสูจน์สมการ Tower of hanoi นี้
$H_n = 2 H_{n-1} + 1$
แล้วออกมาได้เป็น$ 2^{(n+1)} ? 1 $แต่คำตอบที่จริงคือ$ 2^n ? 1$

ช่วยพิสูจน์ให้ดูทีครับ

[nooonuii]

มันก็สูตรเดียวกันนั่นแหละครับ แต่ต่างกันที่ค่าเริ่มต้น

โจทย์เขากำหนด $H_0=1$ หรือ $H_1=1$ เป็นค่าเริ่มต้นล่ะครับ

[GranDAnGlE]

H1 = 1 ครับผม

[nooonuii]

ลองสังเกตความสัมพันธ์ของตัวเลขดีๆก็จะเข้าใจครับ

$H_n=2^1H_{n-1}+1$

$~~~=2(2H_{n-2}+1)+1$

$~~~=2^2H_{n-2}+2^1+1$

$~~~=2^2(2H_{n-3}+1)+2^1+1$

$~~~=2^3H_{n-3}+2^2+2^1+1$

$~~~~\vdots$

$~~~=2^{n-1}H_{n-(n-1)}+2^{n-2}+\cdots + 2^1+1$

$~~~=2^{n-1}H_1+2^{n-2}+\cdots+2^1+1$

$~~~=2^{n-1}+2^{n-2}+\cdots+2^1+1$

$~~~=2^n-1$

[GranDAnGlE]

ขอบคุณคับ
ผมคงจะดู สูตรผลรวมผิดครับ