Recurrence relations: cashier has no change 
A movie theater charges \$10 for a ticket. The cashier starts out with
  no change. Each customer either pays with a \$10 bill, or else pays
  with a $\$20$ bill and receives a $10 bill in change. One evening the
  cashier serves 2n customers. He is always able to provide change when
  required, but at the end of the evening has no \$10 bills left. Find a
  recurrence relation and initial conditions for the number of ways a(n)
  in which this can occur.

My prof also added a note that this recurrence relation is non-linear, but since to my understanding, we have only focused on linear and homogeneous relations, I am not sure how to go about this problem. 
I'm not sure where to go from what I know so far:


*

*the cashier can only start by receiving \$10 and end his shift by receiving a $\$20$ bill

*the number of times he receives both types of bills must be equal to each other

 A: Define $a_k$ to be the change in the amount of 10\$ bills in the cashier, after costumer $k$ pays. Now define, $S_k$ to be the the amount of 10\$ bills in the cashier after costumer $k$, that means $S_k=\sum_{j=1}^ka_j$ (because the cashier starts with no cash).
By the details provided, we can conclude:


*

*$S_k \geq 0$ always.

*$S_{2n} = 0$

*$a_1 = (+1)$ and $a_{2n} = (-1)$


So this problem is equivalent to finding the number of Dyck words of length $2n$.
Let $A_n$ be the number of options in for the described scenario for $2n$ costumers. Trivially $A_0=A_1=1$. Now, suppose we know the values of $A_0,\dots,A_{n-1}$ and we want to know the value of $A_n$. Note that if we fix some integer $1 \leq j_0 \leq n$ and constrain ourselves only to the cases where: $$\begin{cases}S_j \geq 1, \quad \text{if} \ \ 0<j<2j_0 \\ S_{2j_0}=0\end{cases}$$
we can use $A_0,\dots,A_{n-1}$ to get the number options. Lets use $F_{j_0}$ to note the number of options under the constraint , we know already that $a_0 = (+1)$ and thanks to the constraint on $F_{j_0}$ we also know the $a_{2j_0 -1} = (-1)$. So we can devide the problem under the constraint to two distinct and independent sequences of "customers" (words, sequences, etc.). One is customers $a_2,..a_{2j_0-1}$ (under the constraint that $\sum_{k=2}^{2j_0-1}a_k\geq 0$, which is equivalent to considering $a_1,..a_{2j_0}$ with $S_k \geq 1$), which is equal to $A_{j_0-1}$. The second is $a_{2j_0+1},\dots,a_{2n}$, which is equal to $A_{2n-j_0}$.
So we have now: $$F_{j0}=A_{j_0-1}\cdot A_{n-j_0}$$
Consider the sum $\sum_{j=1}^nF_j$, because $j$ is (equivalently) defined to be the first index in which the cashier reaches $0$  10\$ bills, then different $F_j$'s don't double count cases. Thus: $$A_n = \sum_{j=1}^nF_j = \sum_{j=1}^nA_{j-1} A_{n-j} $$
By the way: this is called the Catalan number $n$, and it to turns out to come up in several places in combinatorics.
