1. Show that [F(n+1)]2= [F(n)]2+ F(n-1) F(n+2), Vn 2. 2. Show that F(i)= F(n+2)-1. 3....

Transcribed Image Text:

1. Show that [F(n+1)]2= [F(n)]2+ F(n-1) F(n+2), Vn ≥ 2. 2. Show that F(i)= F(n+2)-1. 3. Consider the following disk transportation problem: You are given three pegs named A, B and C. On peg A sit n disks in strict decreasing order of size, with the smallest disk on the top and the largest disk on the bottom. You are required to transport the disks from peg A to peg C, while respecting the following rules: (a) In each move, exactly one disk can be moved. (b) No disk may ever be placed on top of a smaller disk. (c) Each move consists of taking the uppermost disk from one of the pegs and placing it on top of another peg i.e.. a disk can only be moved if it is the uppermost disk on a peg. Write down a recurrence relation for computing the total number of moves required to transfer the n disks from peg A to peg C. Hint: Do you see why peg B is required? 1. Show that [F(n+1)]2= [F(n)]2+ F(n-1) F(n+2), Vn ≥ 2. 2. Show that F(i)= F(n+2)-1. 3. Consider the following disk transportation problem: You are given three pegs named A, B and C. On peg A sit n disks in strict decreasing order of size, with the smallest disk on the top and the largest disk on the bottom. You are required to transport the disks from peg A to peg C, while respecting the following rules: (a) In each move, exactly one disk can be moved. (b) No disk may ever be placed on top of a smaller disk. (c) Each move consists of taking the uppermost disk from one of the pegs and placing it on top of another peg i.e.. a disk can only be moved if it is the uppermost disk on a peg. Write down a recurrence relation for computing the total number of moves required to transfer the n disks from peg A to peg C. Hint: Do you see why peg B is required?

Answer rating: 100% (QA)

1 To show the recurrence relation Fn1Fn2Fn1Fn2 for the given sequence Fn we need to use the definition of sequence and show that this relation holds f... View the full answer