$n$ people are sitting at a round table with $n$ seats at a restaurant.
The restaurant has only 2 dishes, steak and salad. How many ways are there for the diners to choose a dish, such that no 2 adjacent diners have steak?
Here's what I did:
I tried to solve it with recurrence relation. Let's number the seats $1,...,n$, such that the guy in chair 1 orders first and so on. let $f(n)$ be the number of different valid orders.
The guy in the first chair can order whatever he wants. Let's suppose he orders the salad.
In that case, the guy in the second chair can order whatever he wants (since the guy next to him didnt order steak). so you could say that if the guy in chair $1$ ordered salad, there are $f(n-1)$ options for the other guys.
Now, if the guy in chair $1$ orders steak, then that means the guy in chair $2$ must order a salad, and then the guys in chairs $3,...,n-1$ can order whatever they want (that's $f(n-3)$ options) and then the guy in chair $n$ must order salad as well. so thats $f(n-3)$ options.
Overall we get $f(n)=f(n-1)+f(n-3)$ and now we just solve the recurrence relation.
Would this work?