Here is a problem I am trying to do.
For each positive integer n, let
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
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
we can make use of the inductive hypothesis and conclude that
but after this point, I am stuck. Any hints ?