Series Induction problem set:

Question

For all $n$ belonging to $\mathbb N$, let $A_n$ be the number of subsets of $\{1,2,\ldots,n\}$ that do not contain any two consecutive members (including $\emptyset$);

(a) Show that $A_n$ is the $(n+2)^\text{th}$ Fibonacci Number.

Answer 1

Denote set of the subsets of $\left\{ 1,\dots,n\right\} $ that do not contain two consecutive numbers by $\mathcal{A}_{n}$.

Then $A_{n}$ is the cardinality of $\mathcal{A}_{n}$.

Note that $\mathcal{A}_{n}=\mathcal{A}_{n-1}\cup\left\{ T\cup\left\{ n\right\} \mid T\in\mathcal{A}_{n-2}\right\} $.

These sets are disjoint so that $A_{n}=A_{n-1}+A_{n-2}$.