The elements in a recursive set I have a set of numbers that is defined in the following way:
$a_1 = \{1,-1\}$
$a_2 = \{2,0,0,-2\}$
$a_3 = \{3,1,1,-1,1,-1,-1,-3\}$
$a_n = \{a_{n-1} +1 , a_{n-1} -1 \}$
i.e. at each step we construct a new set $A_n$ by the elements of  $A_{n-1}$ by adding one to all the elements in $A_{n-1}$, and subtract one from all the elements in $A_{n-1}$
I need to show that the elements in $A_n$ are $n-2k$ for $k=0, \dots, n$. with binom multiplicity. i.e. each elemnt $n-2k$ appears $\dbinom{n}{k}$
by intuition this is very obvious, but I just can't seem to think of a formal proof.
 A: It’s a fairly straightforward induction: the construction of the sets $A_n$ mimics the construction of Pascal’s triangle. For the induction step suppose that the elements of $A_n$ are the integers $n-2k$ for $k=0,\dots,n$, each with multiplicity $\binom{n}k$. The elements of $A_{n+1}$ are therefore going to be the integers $n-2k-1$ and $n-2k+1$ for $k=0,\dots,n$. These can be written $(n+1)-2(k+1)$ and $(n+1)-2k$, respectively. As $k$ runs from $0$ through $n$, $k+1$ runs from $1$ through $n+1$, so when you combine these you’re getting the numbers $(n+1)-2k$ for $k=0,\dots,n+1$, exactly as you want. Now you just have to count them.
Consider the number $(n+1)-2k$. You get it by adding $1$ to $n-2k$, and also by subtracting $1$ from $n-2(k-1)$. There are $\binom{n}k$ copies of $n-2k$ in $A_n$, and there are $\binom{n}{k-1}$ copies of $n-2(k-1)$. Now just put the pieces together.
A: It is useful to regard the elements of the set $a_{n}$ as the exponents $m$ that occur in the expansion of the power $$A_{n} = (x+x^{-1})^{n},$$ and then the coefficient of $x^{m}$ is the required multiplicity. 
Now $$A_{n} = x^{n} (1 + x^{-2})^{n},$$ so binomial expansion tells you that the exponents that occur are indeed the $n - 2 k$, for $k = 0, 1, \dots n$, and that the multiplicities are binomial.
A: Every instance of an element $x\in a_n$ has a unique history of production: it either came from an instance $x-1\in a_{n-1}$ or from an instance $x+1\in a_{n-1}$, and by induction that instance has its own history. (To start off the induction put $a_0=\{0\}$ and give its unique element $0$ an empty history. To record the history, associate to each instance $x\in a_n$ a string of $n$ symbols L or R, defined by taking the history of the instance $y\in a_{n-1}$ that $x$ was produced from, and adding an L at the end in case $x=y-1$, and otherwise ($x=y+1$) adding an R at the end. For instance the first $-1\in a_3$ which was produced from the first $0\in A_2$ which came from $1\in a_1$ would have history RLL.
An immediate proof by indiction shows that if the history of in instance $x\in a_n$ has $k$ letters L, and thereforr $n-k$ letters R, then $x=k\times-1+(n-k)\times1=(n-k)-k=n-2k$. In other words $k=\frac{x+n}2$ is determined by $x$, and the multiplicity of $x$ equals the number of strings of length $n$ with $k$ letters L and $n-k$ letters R; this number if $\binom nk$.
