Hello Celcius

Welcome to Math Help Forum!Would you like to explain why?

The number of subsets is = the number of binary strings of length . And we may set up a 1-1 correspondence between subsets and strings as follows:(b)

???

Choose any binary string of length , say .Thus the number of subsets that do not contain consecutive integers and and the number of strings that do not contain the sequence are therefore equal.

Create a subset of corresponding to this string by including in it the integer if and excluding it if .

If your answer to part (a) is correct, then this result follows immediately by induction.(c)

I know

and that matches up with

So,

and so on, not sure what to do next.

Assume that, for two consecutive integers , and . Then, using the relation that defines a Fibonacci sequence,

Clearly and and that completes the proof.

, using the answer to (a)

Grandad