Prove that the number of acceptable sequences of integers is $(n+1)!$ 
Let $n$ be a positive integer. A sequence $(a_0,\cdots, a_n)$ of >integers is acceptable if it satisfies the following conditions:

*

*$0= |a_0|<|a_1|<\cdots < |a_{n-1}|<|a_n|$

*The sets $\{|a_1-a_0|,|a_2-a_1|,\cdots, |a_{n-1}-a_{n-2}|,|a_n->a_{n-1}|\}$ and $\{1,3,\cdots, 3^{n-1}\}$ are equal.

Prove that the number of acceptable sequences of integers is $(n+1)!.$

I think this problem can be solved using induction, though the inductive hypothesis may require proving something more general than what the problem asks for. As for the inductive hypothesis, it's basically just the problem statement. For the base case where $n=1$, we just have $|a_1-a_0| = 1$ and $|a_1| > 0$, so $a_1=\pm 1$ are the only possibilities. Now assume the result holds for all $k<n,$ where $n\ge 2$. We need to prove the result for n. $\{|a_1-a_0|,\cdots, |a_n-a_{n-1}|\}$ is some permutation of $\{1,3,\cdots, 3^{n-1}\}$, so in particular, there exists some $i$ such that $3^{n-1} = |a_i-a_{i-1}|$. The terms of smaller index, namely $|a_i-a_{i-1}| $'s can be rearranged in increasing order and one can apply the inductive hypothesis to $\{|a_1-a_0|,\cdots, |a_{i-1} - a_{i-2}|\}$, which gives $i!$ possible acceptable sequences. How can I proceed from here? It would be useful to find the number of possibilities for $a_k$ for $i\leq k < n$, but I'm not sure how.
 A: We can actually prove a more general result via strong induction on $n$ based on this solution.
Lemma Let $\left(b_1, b_2, \ldots, b_n\right)$ be a set of positive integers such that $3 b_i \leqslant b_{i+1}$ for all $i$. Then
$$b_i > 2\sum_{k = 1}^{i - 1} b_k$$.
We know that
$$\frac{b_i}{2} = \frac{b_i}{3} + \frac{b_i}{9} + \cdots \geqslant \sum_{k = 1}^{i - 1} b_k.$$
The two sides are equal only when the sequence $b_i$ is infinite, so the inequality is true.
Now we will prove using strong induction on $n$. Clearly the base case holds. Suppose the statement is true for $n = j - 1$. Now consider some permutation $C = \left\{c_1, c_2, \ldots, c_j\right\}$ of the set $B = \left\{b_1, b_2, b_3, \cdots, b_j\right\}$. Find the element $c_k=b_j$. For the first $k - 1$ elements of $C$, we order them so we can use the inductive hypothesis. The number of acceptable sequences such that the set of differences
$$\left\{|a_1 - a_0|, \ldots, |a_{k - 1} - a_{k - 2}|\right\}$$
is equal to $$\left\{c_1, c_2, \ldots, c_{k-1}\right\}$$
is $k!$.
By our lemma, $$c_k > 2\sum_{m = 1}^{k - 1}c_m =2 \sum_{m = 1}^{k - 1}\left|a_m - a_{m - 1}\right| \geqslant 2\left|a_{k - 1} - a_{k - 2} + a_{k - 2} - a_{k - 3} + \cdots + a_1 - a_0\right|=2\left|a_{k-1}\right|.$$
Thus, $a_k$ is either $a_{k - 1} + c_k$ or $a_{k - 1} - c_k$. It is easy to check that for either possible value of $a_k,\left|a_k\right| > \left|a_{k - 1}\right|$. After that, there is only one possible value for $a_{k + 1}, \ldots, a_j$ because only one of $a_i \pm c_{i + 1}$ will satisfy $\left|a_i\right| > \left|a_{i - 1}\right|$.There are
$$\left(\begin{array}{l}j-1 \\ k-1\end{array}\right)$$
possible ways to choose $c_1, c_2, \ldots, c_{k - 1}$ from $B$. Given those elements of $C$, there are $k!$ ways to make an acceptable sequence $\left(a_0, a_1, \ldots, a_{k - 1}\right)$. Thus, there are two possible values for $a_k$. After that, there are $(j - k)!$ ways to order the remaining elements of $C$, and for each such ordering, there is exactly one possible acceptable sequence $\left(a_0, a_1, \ldots, a_j\right)$. Now, counting up all the possible ways to do this over all values of $k$, we get that the number of acceptable sequences is equal to
\begin{align}
    \sum_{k = 1}^j\left(\begin{array}{c}j - 1 \\ k - 1\end{array}\right) k!(2) 
    (j - k)! &= \sum_{k = 1}^j 2(j - 1)!(k)\\  
    &= 2(j - 1)! \frac{j(j+1)}{2}\\
    &=(j + 1)!
\end{align}
and we are done.
