Lesson test: Recurrences

Recurrences

1.[1p]
What is the fewest number of moves that transfers a Tower of Hanoi of $10$ discs to another peg?

CorrectNot quite: 1023

2.[2p]
In the version of the Tower of Hanoi where a disc may only move to a neighbouring peg, the natural strategy satisfies $a_{n} = 3 a_{n - 1} + 2$ with $a_{0} = 0$ . How many moves does it use for $4$ discs, carried from one end peg to the other?

CorrectNot quite: 80

3.[2p]
Unroll $a_{n} = 3 a_{n - 1} + 4$ with $a_{0} = 1$ and find $a_{5}$ .

CorrectNot quite: 727

4.[2p]
How many bit strings of length $12$ contain no two consecutive 1s?

CorrectNot quite: 377

5.[3p]
How many strings of length $6$ over the alphabet ${a, b, c}$ contain no two consecutive $a$ s?

CorrectNot quite: 448

6.[2p]
Into how many regions do $12$ lines in general position cut the plane?

CorrectNot quite: 79

7.[2p]
Six circles are drawn so that every two cross at two points and no three pass through one point. How many regions do they make?

CorrectNot quite: 32

8.[1p]
With $F_{0} = 0$ and $F_{1} = 1$ , which Fibonacci number counts the bit strings of length $n$ with no two consecutive 1s?

$F_{n + 2}$

Correct

$F_{n + 1}$

The answer is: $F_{n+2}$

$F_{n}$

The answer is: $F_{n+2}$

$F_{2 n}$

The answer is: $F_{n+2}$

9.[3p]
Match each problem to its recurrence.

Tower of Hanoi moves
Bit strings with no two consecutive 1s
Regions cut by lines in general position
Regions cut by circles crossing in pairs

$b_{n} = b_{n - 1} + b_{n - 2}$
$R_{n} = R_{n - 1} + n$
$C_{n} = C_{n - 1} + 2 (n - 1)$
$T_{n} = 2 T_{n - 1} + 1$

Show the answer

Tower of Hanoi moves: $T_{n} = 2 T_{n - 1} + 1$ Bit strings with no two consecutive 1s: $b_{n} = b_{n - 1} + b_{n - 2}$ Regions cut by lines in general position: $R_{n} = R_{n - 1} + n$ Regions cut by circles crossing in pairs: $C_{n} = C_{n - 1} + 2 (n - 1)$

1.[1p] What is the fewest number of moves that transfers a Tower of Hanoi of 10 discs to another peg?

2.[2p] In the version of the Tower of Hanoi where a disc may only move to a neighbouring peg, the natural strategy satisfies an=3an-1+2 with a0=0. How many moves does it use for 4 discs, carried from one end peg to the other?

3.[2p] Unroll an=3an-1+4 with a0=1 and find a5.

4.[2p] How many bit strings of length 12 contain no two consecutive 1s?

5.[3p] How many strings of length 6 over the alphabet {a,b,c} contain no two consecutive as?

6.[2p] Into how many regions do 12 lines in general position cut the plane?

7.[2p] Six circles are drawn so that every two cross at two points and no three pass through one point. How many regions do they make?

8.[1p] With F0=0 and F1=1, which Fibonacci number counts the bit strings of length n with no two consecutive 1s?

9.[3p] Match each problem to its recurrence.

1.[1p]
What is the fewest number of moves that transfers a Tower of Hanoi of $10$ discs to another peg?

2.[2p]
In the version of the Tower of Hanoi where a disc may only move to a neighbouring peg, the natural strategy satisfies $a_{n} = 3 a_{n - 1} + 2$ with $a_{0} = 0$ . How many moves does it use for $4$ discs, carried from one end peg to the other?

3.[2p]
Unroll $a_{n} = 3 a_{n - 1} + 4$ with $a_{0} = 1$ and find $a_{5}$ .

4.[2p]
How many bit strings of length $12$ contain no two consecutive 1s?

5.[3p]
How many strings of length $6$ over the alphabet ${a, b, c}$ contain no two consecutive $a$ s?

6.[2p]
Into how many regions do $12$ lines in general position cut the plane?

7.[2p]
Six circles are drawn so that every two cross at two points and no three pass through one point. How many regions do they make?

8.[1p]
With $F_{0} = 0$ and $F_{1} = 1$ , which Fibonacci number counts the bit strings of length $n$ with no two consecutive 1s?

9.[3p]
Match each problem to its recurrence.