The problem statement is as follows: There are N people standing in a row. The ith person is standing in the ith position. In how many ways can we arrange the people so that each person is either in their own position or in their adjacent position?

I figured that The answer follows the Finonacci pattern.

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?

my attempt:

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] 

CodePudding user response：

By induction:

As you've shown, your statement is true for small values. Suppose it's true that for every positive integer up to n there are Fib(n) arrangements that meet your criterion. Then, we add a person.

Our new person can occupy two positions: the n'th and (n 1)'st.

In the latter case, we count the Fib(n) ways of arranging the first n items. In the former case it must be that the (n 1)'st and n'th are switched, and there are Fib(n-1) ways of arranging the first n-1 people.

Since Fib(n-1) Fib(n) = Fib(n 1), we've proved your theorem by induction.