How many permutations $\pi$ of $\{1,2,...,n\}$ are there such that $|\pi (i) - i|\le 1$?

Question

How many permutations $\pi$ of $\{1,2,...,n\}$ are there such that $|\pi (i) - i|\le 1$?

How would I go about solving this with a proof and teaching it to a non-math major student?

Answer 1

Let $f(n)$ denote tha number of such permutations. Let $\pi$ be such a permutation. Either $\pi(n)=n$ and the restriction to $\{1,\ldots,n-1\}$ is one of $f(n-1)$ smaller permutations of this kind. Or $\pi(n)=n-1$, necessarily $\pi(n-1)=n$ and the restriction to $\{1,\ldots,n-2\}$ is one of $f(n-2)$ smaller such permutations. We obtain the recursion $$f(n) = f(n-1)+f(n-2).$$ We check $f(1)=1$, $f(2)=2$ and therefore conclude that $f(n)$ is the $n$th Fibonacci number.