问题陈述如下：有N个人站在一排。第i个人站在第i个位置。我们可以通过多种方式安排人员，使每个人要么处于自己的位置，要么处于相邻的位置？
我想答案遵循Finonacci模式。
like if N = 1,
The answer is 1. If N = 2, the answer is 2.
If N = 3, then the answer is 3, if N = 4, then the answer is 5, and so on.
This is via observation. Can you provide concrete proof why this is always true?
我的尝试：
If the (N-1)th number is in its own position, then we can't
do any change and the answer is just ans[N-1]. Otherwise,
swap Nth and (N-1)th position and it will give arrangements ans[N-2]
so final ans[N] = ans[N-1]+ans[N-2]
通过归纳：
正如您所展示的，您的声明对于小值是正确的。假设每一个达到n的正整数都有符合您标准的Fib(n(排列，这是真的。然后，我们添加一个人。
我们的新人可以占据两个位置：第n个和第(n+1(个。
在后一种情况下，我们计算排列前n个项目的Fib(n(方式。在前一种情况下，必须切换(n+1(的第n个和第n个，并且有Fib(n-1(种方式来安排前n-1个人。
由于Fib(n-1(+Fib(n(=Fib(n+1(，我们已经用归纳法证明了你的定理。