Find number of restricted compositions of n How to find the total number of compositions of n where no part is equal to 2.
More generally, how to find the number of compositions with restrictions such as this, where certain integers are not allowed?
Edit: How to find the recurrence relation - I am looking for a combinatorial proof . Solving in a different method, I got that the recurrence relation is:
$a_n +a_{n-2}=2a_{n-1}+a_{n-3}$
Thanks 
 A: It’s not hard to find the generating functions, at least. Let $A$ be the set of allowable parts; then the number of compositions of $n$ into exactly $k$ allowable parts is easily seen to be
$$[x^n]\left(\sum_{a\in A}x^a\right)^k\;.$$
Since
$$\frac1{1-\sum_{a\in A}x^a}=\sum_{k\ge 0}\left(\sum_{a\in A}x^a\right)^k\;,$$
the number of compositions of $n$ into allowable parts is
$$[x^n]\left(\frac1{1-\sum_{a\in A}x^a}\right)\;.$$
If $A=\Bbb Z^+\setminus\{2\}$, this is
$$[x^n]\left(\frac1{1-x-\sum_{a\ge 3}x^a}\right)=[x^n]\left(\frac1{1-x-\frac{x^3}{1-x}}\right)=[x^n]\left(\frac{1-x}{1-2x+x^2-x^3}\right)\;.$$
Added: This clearly implies that $a_n$, the number of allowable compositions of $n$, satisfies the recurrence
$$a_n=2a_{n-1}-a_{n-2}+a_{n-3}\;.$$
To derive this combinatorially, suppose that $m_1+\ldots+m_k$ is a composition of $n$. If $m_1=1$, this composition is obtained by adding $1$ at the beginning of the allowable composition $m_2+\ldots+m_k$ of $n-1$. Conversely, every allowable composition of $n-1$ can be extended to an allowable composition of $n$ by adding $1$ at the beginning. Thus, $n$ has $a_{n-1}$ allowable compositions that begin with $1$.
If $m_1+m_2+\ldots+m_k$ is an allowable composition of $n-1$, we can also produce the composition $(m_1+1)+m_2+\ldots+m_k$ of $n$, which will be allowable if and only if $m_1\ne 1$. We just saw that $n-1$ has $a_{n-2}$ allowable compositions beginning with $1$, so this procedure of adding $1$ to the first term of a composition of $n-1$ produces $a_{n-1}-a_{n-2}$ allowable compositions of $n$ that do not start with $1$.
However, this procedure does not produce any composition of $n$ that begins with $3$, since that would require starting with a non-allowable composition of $n-1$. To get the allowable compositions of $n$ that begin with $3$, we must start with an allowable composition of $n-3$ and add $3$ at the beginning. There are $a_{n-3}$ such compositions, so altogether we have
$$a_n=a_{n-1}+(a_{n-1}-a_{n-2})+a_{n-3}=2a_{n-1}-a_{n-2}+a_{n-3}\;.$$
A: The "combinatorial proof" of the recurrence relation:
$$ a_n = 2a_{n-1} - a_{n-2} + a_{n-3} $$
as given by Chinn and Heubach (2003), Thm. 1, is in agreement with what Brian M. Scott provides:

The compositions of $n$ without $2$’s can be generated recursively from those of $n − 1$ by either appending a $1$ or by increasing the last summand by $1$. However, this process does not generate those compositions ending in $3$, which we generate separately by appending a $3$ to the compositions of $n − 3$. Furthermore, we must delete the compositions of $n − 1$ that
  end in $1$, since increasing the terminal $1$ would produce a composition of $n$ that ends in $2$.  The number of such compositions corresponds to the number of compositions of $n − 2$.

As to more general problems "with restrictions such as this," there are many ways to ask about compositions with restrictions on values of parts.  The Wikipedia article uses the phrase "A-restricted compositions" to mean those whose parts are in an allowed set of values $A$, while some authors use the phrase "S-restricted compositions" for set $S$ of allowed parts.  
Problems where the parts are restricted to an interval of (integer) values were previously discussed here at Math.SE.  These problems can be reduced to ones where the largest part does not exceed a fixed bound, (Malandro, 2012), where the terminology $L$-compositions of $n$ is used for those with parts taken from a set $L$ of positive integers.
Finally there is on-going interest in efficient algorithms for generating restricted integer compositions.
