3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Related to this. Have a look at the answer on that question. Also this can help. $\endgroup$ – drhab Feb 9 '15 at 18:27
  • $\begingroup$ @drhab This is not fibonacci at all as 4 is NOT fibonacci number $\endgroup$ – user3786422 Feb 9 '15 at 18:29
  • $\begingroup$ That is because he is forced to take at least one. $5$ is a Fibonacci number $\endgroup$ – drhab Feb 9 '15 at 18:30
  • $\begingroup$ @drhab U mean (n+2)th fibonacci number -1 is answer ? $\endgroup$ – user3786422 Feb 9 '15 at 18:31
  • 1
    $\begingroup$ I think so, yes. Try it out on some small numbers to find confirmation. $\endgroup$ – drhab Feb 9 '15 at 18:33
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.