Proving Fibonacci Number as Permutations with Restriction |p(k)-k| \leq 1

[alec_tronn]

Homework Statement

Prove that the number of permutations p on the set {1,2,3,...,n} with the property that |p(k)-k| $$\leq$$ 1, for all 1$$\leq$$k$$\leq$$n, is the fibonacci number f$$_{n}$$

The Attempt at a Solution

I guess I don't understand what it's asking. I thought I knew what a permutation was... but now I'm really confused. Can someone please restate this problem in a way that maybe I could understand? Thanks a lot!

 

[Dick]

Consider constructing one of those permutations, to pick the first number I need to satisfy |p(1)-1|<=1. So p(1) can only be 1 or 2. Similarly p(2) can only be 1,2 or 3. p(3) can be 2,3 or 4. Etc.