Towers of Hanoi Explicit Formula: Proof Using Mathematical Induction

To Prove: If a sequence satisfies the recurrence relation

m_n

= 2m_n – 1 + 1, for n ³ 2,

and the initial condition m₁ = 1, then

m_n

= 2ⁿ – 1 for all positive integers n.

Remarks	Proof: Given a sequence satisfying the recurrence relation m_n = 2m_n – 1 + 1, for n ³ 2 and the initial condition m₁ = 1, then let P(n): m_n = 2ⁿ – 1 for all positive integers n.
Show the statement works for n = 1.	(1) Clearly the formula is correct for n = 1 because 2¹ – 1 = 2 – 1 = 1 = m₁.
[Assume it works for some arbitrary integer k, and show that it works for k + 1.] Write out our initial statement as an assumption in k, say P(k).	(2a) Suppose the formula is correct for some integer k, where k ³ 1. m_k = 2^k –1.
Write out the statement for P(k + 1) Utilize the inductive hypothesis: substitute into the formula for P(k + 1). Now simplify to see if the statement is true for k + 1.	(2b) We must show that P(k + 1) is true. From the recurrence relation we know that m_k + 1 = 2m_k + 1. So m_k + 1 = 2(2^k – 1)+ 1 m_k + 1 = 2^k + 1 – 2 + 1 m_k + 1 = 2^k + 1 – 1. Hence P(n) is true for all n ³ 1.