hi

Here is a problem I am trying to do.

For each positive integer n, let

and

For example,

Prove that for every n, the number of elements in is

, the Fibonacci number.

for example , the number of elements in is .

there is one hint given in the problem...

Hint: Which elements of contain ? Which don't ?

The answers to both questions are related to the elements of

for certain ....

now I see that elements of does not contain .

So let me put the goal as

Let

so my goal now becomes ( for strong induction problem)

So we let n be arbitrary and suppose that

I start by proving base cases for n=1,2 . So consider the next case of

Since

and

we can make use of the inductive hypothesis and conclude that

and

but after this point, I am stuck. Any hints ?