Thread: strong induction problem involving power set

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 ?

Originally Posted by issacnewton

hi

Here is a problem I am trying to do.

For each positive integer n, let



and

Where