# strong induction problem involving power set

• Oct 7th 2011, 11:17 PM
issacnewton
strong induction problem involving power set
hi

Here is a problem I am trying to do.

For each positive integer n, let

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

and

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

For example,

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

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

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

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

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

So let me put the goal as

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

Let

$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)

$\forall n[(\forall k

So we let n be arbitrary and suppose that

$\forall k

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

Since

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

and

$1\leqslant (n-1)

we can make use of the inductive hypothesis and conclude that

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

and

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

but after this point, I am stuck. Any hints ?
• Oct 8th 2011, 02:32 AM
CaptainBlack
Re: strong induction problem involving power set
Quote:

Originally Posted by issacnewton
hi

Here is a problem I am trying to do.

For each positive integer n, let

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

and

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

$P_{n+1}=P_n \cup P^*_{n-1}$

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