What is wrong with my approach?

Question

Q) There are 2k+1 people sitting around a circular table , let them be $P_1,P_2,...,P_{2k+1}. P_1$ is sitting between $P_2$ and $P_{2k+1}.P_2$ sitting between ${P_1}$ and ${P_3}$ and so on.Find the number of ways to select non empty subset of these people, such that no two adjacent people are selected.The subset can be of any size. For e.g. :
For k=2, the possible groups are (1),(2),(3),(4),(5),(1,3),(1,4),(2,4)(2,5),(3,5) and no more subsets with 3 or more elements are possible.

My Approach: Let the even no. be selected and space are represented as _.Therefore, sequence now:
_2_4_6_8_10_12......2k-2_2k_. The dashes are to be filled with odd numbers(except 2k+1 as 1 and 2k+1 are sitting together) such that (1,3) don't come with 2 or (3,5) don't come with 5 and so on (so as consecutive elements are not selected). So the first dash is filled with any of k-1 elements,second with k-1 elements and total ways is k-2 * k-2 * k-2 * k-3 * ..... *1 elements. Add the same, as it is done by taking 2k+1 as an element instead of 1 and the total cases now(including both): 2 * k-2 * k-2 * k-2 * ..... *1. I did the same and added them by reducing it the sizes of elements,and I am unable to reach the correct answer with this.What is wrong with this approach? Also is there a shorter way to do the question?

Correct answers: For k=5; number of such sets = 198
For k=6;number of such sets=520
For k=7;number of such sets=1363

Answer 1

Hint: It is easier to solve the problem by recurrence for all $n$, not just odd number of people.

Let $a_n$ be the number of ways to select these people with the above conditions.

Show that $a_n = a_{n-1} + a_{n-2} + 1$ for $n\geq 4$. The +1 follows because we have to choose non-empty people.

Clearly we have $a_2 = 2, a_3 = 3$. From here, we can find that $a_{11} = 198, a_{13} = 520, a_{15} = 1363.$

---

Let $L_n$ be the number of ways to select $n$ people in a line, no 2 consecutive. We allow for possibly selecting 0 people.

We want to create a recurrence relation for $L_n$.
Let's consider the cases where person 1 is selected. Person 2 cannot be selected, and persons 3 to $n$ just have to obey the "no 2 consecutive" rule, so there are $L_{n-2}$ ways to select them.
Let's consider the cases where person 1 is not selected. Persons 2 to $n$ just have to obey the "no 2 consecutive" rule, so there are $L_{n-1}$ ways to select them.
Hence, we can conclude that:

$$L_n = L_{n-2} + L_{n-1} $$

Let $C_n$ be the number of ways to select $n$ people in a circle, no 2 consecutive. We allow for possibly selecting 0 people.
By conditioning on whether 1 is selected or not, we have

$$ \begin{array} {l l } C_n & = L_{n-3} + L_{n-1} \\ & = L_{n-4} + L_{n-5} + L_{n-2} + L_{n-3} \\ & = C_{n-1} + C_{n-2} \end{array}$$

Clearly $a_n = C_n - 1 $. So $a_n = a_{n-1} + a_{n-2} + 1$

Answer 2

Actually, we can “flatten” the table to a row, and then throw away the bad choices. We have this result:

(Key Step) There are $n$ people sitting in a row. The number of ways to choose $m$ people from $P_1, P_2, \dots, P_n$ with no consecutive people chosen is $\binom{n-m+1}{m}$

Now we can just remove the “bad” ones, which is when $P_1$ sits with $P_n$

There are $n$ people sitting in a round table. The number of ways to choose $m$ people from $P_1, P_2, \dots, P_n$ with no consecutive people chosen is $\binom{n-m+1}{m}-\binom{n-m-1}{m}$

Now you can just sum from $m=1$ to $m=k$ with $n=2k+1$.

The difficulty from this problem comes from (Key Step), but I think it’s quite a well known combinatorial problem