Welcome to Math Help Forum!
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)
and that matches up with
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)