Design and Analysis of Algorithms

738 Design and Analysis of Algorithms

E.1.12 Appendix D: Solutions of Recurrence Relations

1. There are n seating positions arranged in a line. Prove that the number of ways of choosing a subset of

these positions, with no two chosen positions consecutive, is Fibonacci number F

n + 1

.

2. If the n positions are arranged around a circle, show that the number of choices is F

n

+ F

n–2

for n ≥ 2.

3. Prove the following identities:

(i)

2

11nnn

F

FF

+−

−

= (– 1) for n ≥ 1.

(ii)

2

0

n

in

i

FF

+

=

=

∑

– 1

(iii)

22

12nnn

FFF

−

+=

, F

n–1

F

n

+ F

n

F

n+1

= F

2n+1

.

(iv)

⎣⎦

/2

0

n

n

i

ni

F

i

=

−

⎛⎞

=

⎜⎟

⎝⎠

∑

.

4. Show that F

n

is composite for all odd n > 3. By a previous result, F

2n + 1

= ...