3

There are N plant pots available in nursery placed in a straight line. Bob is planning to take few of these pots. But whatever number of pots he is going to take, he will take no two successive pots.(i.e. if he is taking a pot i from nursery, he will not take i-1 and i+1 pots.)

So given N, we need to calculate how many different set of pots he could select. He need to take at least one pot from nursery.

Example : Let N=3 then answer is 4. Please help to solve this problem

user3786422
  • 245

1 Answers1

1

Let $a_n$ denote the number of subsets that can be selected from $n$ pots given that at least one is taken and no two consecutive pots are taken.

Number the pots from $1$ to $n$ so that we are considering subsets of $\{1, 2, \ldots, n\}$.

$a_1 = 1$ since the only possible selection is $\{1\}$

$a_2 = 2$ since the only possible selections are the singleton sets $\{1\}, \{2\}$.

$a_3 = 4$ since the only possible selections are $\{1\}, \{2\}, \{3\}, \{1, 3\}$.

$a_4 = 6$ since the only possible selections are $\{1\}, \{2\}, \{3\}, \{4\}, \{1, 3\}, \{1, 4\}, \{2, 4\}$.

Note that when $n = 4$, there are three types of selections that can be made:

  1. the allowable subsets of $\{1, 2, 3\}$, of which there are $a_3$;
  2. the union of the set $\{4\}$ with each of the allowable subsets of $\{1, 2\}$, of which there are $a_2$;
  3. the singleton set $\{4\}$.

In general, the allowable subsets of $\{1, 2, \ldots, n\}$, where $n \geq 3$, consist of

  1. the allowable subsets of $\{1, 2, \ldots, n - 1\}$, of which there are $a_{n - 1}$;
  2. the union of the set $\{n\}$ with each of the allowable subsets of $\{1, 2, \ldots, n - 2\}$, of which there are $a_{n - 2}$ since $n$ can only be paired with elements that are less than $n - 1$;
  3. the singleton set $\{n\}$.

Hence, \begin{align*} a_1 & = 1\\ a_2 & = 2\\ a_n & = a_{n - 1} + a_{n - 2} + 1, n \geq 3 \end{align*} Since $a_1 = F_3 - 1$ and $a_2 = F_4 - 1$, where $F_n$ denotes the $n$th Fibonacci number, this suggests that $$a_n = F_{n + 1} - 1 + F_{n} - 1 + 1 = F_{n + 2} - 1$$ which can be proved by induction using the observations above.

N. F. Taussig
  • 76,571