# Thread: strong induction problem involving power set

1. ## strong induction problem involving power set

hi

Here is a problem I am trying to do.

For each positive integer n, let

$\displaystyle A_n=\{1,2,\cdots,n\}$

and

$\displaystyle P_n=\{X\in \mathcal{P}(A_n)\lvert \;\mbox{X does not contain two consecutive integers }\;\}$

For example,

$\displaystyle P_3=\{\varnothing,\{1\},\{2\},\{3\},\{1,3\}\}$

Prove that for every n, the number of elements in $\displaystyle P_n$ is
$\displaystyle F_{n+2}$, the $\displaystyle (n+2)^{\mbox{th}}$ Fibonacci number.

for example , the number of elements in $\displaystyle P_3$ is $\displaystyle 5=F_5$.

there is one hint given in the problem...
Hint: Which elements of $\displaystyle P_n$ contain $\displaystyle n$ ? Which don't ?
The answers to both questions are related to the elements of $\displaystyle P_m$
for certain $\displaystyle m<n$ ....

now I see that elements of $\displaystyle P_{n-1}$ does not contain $\displaystyle n$.

So let me put the goal as

$\displaystyle \forall n\geqslant 1[P_n\;\mbox{has}\;F_{n+2}\;\mbox{elements}]$

Let

$\displaystyle Q(n)=[(n\geqslant 1)\Rightarrow(P_n\;\mbox{has}\;F_{n+2}\;\mbox{elem ents})]$

so my goal now becomes ( for strong induction problem)

$\displaystyle \forall n[(\forall k<n Q(k))\Rightarrow Q(n)]$

So we let n be arbitrary and suppose that

$\displaystyle \forall k<n Q(k)\;\mbox{and}\; n\geqslant 1$

I start by proving base cases for n=1,2 . So consider the next case of
$\displaystyle n\geqslant 3$

Since

$\displaystyle 1\leqslant (n-2)< n$

and

$\displaystyle 1\leqslant (n-1)<n$

we can make use of the inductive hypothesis and conclude that

$\displaystyle P_{n-1}\;\mbox{has}\;F_{n+1}\;\mbox{elements}$

and

$\displaystyle P_{n-2}\;\mbox{has}\;F_{n}\;\mbox{elements}$

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

2. ## Re: strong induction problem involving power set

Originally Posted by issacnewton
hi

Here is a problem I am trying to do.

For each positive integer n, let

$\displaystyle A_n=\{1,2,\cdots,n\}$

and

$\displaystyle P_n=\{X\in \mathcal{P}(A_n)\lvert \;\mbox{X does not contain two consecutive integers }\;\}$
$\displaystyle P_{n+1}=P_n \cup P^*_{n-1}$

Where $\displaystyle P^*_{n-1}=\{ a \cup \{(n+1)\}; a\in P_{n-1} \}$