It seems curious to ask for a combinatorial proof of this relation, which is not obvious at all. However it follows easily from the recurrence: $ P_{n+2}+P_{n-2}=P_{n+1}+P_n+P_{n-2}=(P_n+P_{n-1})+P_n+P_{n-2} = 3 P_n. $ You can turn this into a bijection, but it is a bit artificial. Given a paving of either $1\times(n+2)$ or of $1\times(n-2)$, find a paving of $1\times n$ and a number $i\in\{1,2,3\}$ as follows. If the paving was of $1\times(n+2)$, and the last two squares form a sub-paving, then we get a paving of $1\times n$ by removing them, and set $i$ to the number of tiles ($1$ or $2$) used for the final two squares. We are left with the cases of a paving of $1\times(n+2)$ that ends with $(2,1)$ or any paving of $1\times(n-2)$; we set $i=3$ for those cases, and pave $1\times n$ by replacing the $(2,1)$ by $(1)$ in the former case or by adding a dimer $(2)$ in the latter case. One checks that for any given paving of $1\times n$ and $i\in\{1,2,3\}$ one uniquely reconstructs a paving of either $1\times(n+2)$ or of $1\times(n-2)$.