Explain tower of hanoi problem and give its recurrence relation
Answers
Answered by
4
Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. ... 1) Only one disk can be moved at a time. 2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
Answered by
0
You’re just missing a little algebra. You have Un=Tn+1Un=Tn+1 for all n≥0n≥0, so Un−1=Tn−1+1Un−1=Tn−1+1, and therefore 2Tn−1+2=2(Tn−1+1)=2Un−12Tn−1+2=2(Tn−1+1)=2Un−1. Combine this with Tn+1=2Tn−1+2Tn+1=2Tn−1+2, and Un=Tn+1Un=Tn+1, and you get Un=2Un−1Un=2Un−1, with U0=1U0=1.
Now notice that UnUn is just doubling each time nn is increased by 11:
U1U2U3U4=2U0=2U1=22U0=2U2=23U0=2U3=24U0U1=2U0U2=2U1=22U0U3=2U2=23U0U4=2U3=24U0
The pattern is clearly going to persist, so we conjecture that Un=2nU0Un=2nU0 for each n≥0n≥0. This is certainly true for n=0n=0. Suppose that it’s true for some n≥0n≥0; then
Un+1=2Un=2⋅2nU0=2n+1U0,Un+1=2Un=2⋅2nU0=2n+1U0,
and the conjecture follows by mathematical induction.
Now we go back and use the fact that U0=1U0=1 to say that Un=2nUn=2n for each n≥0n≥0, and hence Tn=Un−1=2n−1Tn=Un−1=2n−1.
Now notice that UnUn is just doubling each time nn is increased by 11:
U1U2U3U4=2U0=2U1=22U0=2U2=23U0=2U3=24U0U1=2U0U2=2U1=22U0U3=2U2=23U0U4=2U3=24U0
The pattern is clearly going to persist, so we conjecture that Un=2nU0Un=2nU0 for each n≥0n≥0. This is certainly true for n=0n=0. Suppose that it’s true for some n≥0n≥0; then
Un+1=2Un=2⋅2nU0=2n+1U0,Un+1=2Un=2⋅2nU0=2n+1U0,
and the conjecture follows by mathematical induction.
Now we go back and use the fact that U0=1U0=1 to say that Un=2nUn=2n for each n≥0n≥0, and hence Tn=Un−1=2n−1Tn=Un−1=2n−1.
Similar questions