Number of possible sequences with at most 2 repetitions and entry $a_i \in\{1,2,3,\dots,i\}$ We denote the first $k$ natural numbers (not including 0) by $N_k = \{1,2,3,4,\dots, k\}$.
Consider a length $n$ sequence,  $S=(s_1,s_2,s_3,\dots,s_n)$ such that $s_1 \in N_1$, $s_2 \in N_2$ and more generally $s_i \in N_i$. 
Let $S_n$ denote the set of such sequences. The number of possible different sequences, $\lvert S_n \rvert$ of length $n$ is $n!$  since there are 1 choices for $s_1$ 2 choices for $s_2$ and so on.
Let $S^2_n$ denote the set of sequences 
$$ S^2_n  = \{ S \in S_n : \text{no number occurs more than twice in $S$} \}    $$
For example $S = (1,1,1,2,3) \in S_5$ but not in $S^{2}_5$ since 1 occurs 3 times in $S$.  
Question: Calculate $\lvert S_n^2 \rvert$ for each $n$.
I have tried to find a suitable recurrence and by observation it appears that
$$ \lvert S_n^2 \rvert  = n\lvert S_{n-1}^2 \rvert - (n-2)^2 
$$ 
Unfortunately I do not know how to prove this and help would be greatly appreciated.  
 A: We begin with $|S_1^2| = 1$
For $n=2$, $|S_2^2| = 2$, for which $1$ case already has two repeated numbers.
For $n=3$, $|S_3^2| = 3+2$, $3$ cases that result from the previous element that has no repeated elements and 2 that come from the element which already had one repeated element. Observe that from this $5$ elements $2+2=4$ have at least one repeated element ($2$ from the one that already had a repeated element and $2$ which come from repeating a number from the one that didn't have a repeated element.
With these observations I think that:
$$|S_n^2|= n + \sum_{K=1}^{\lfloor\frac{n}{2}\rfloor}(\text{number of elements of $S_{n-1}$ with $K$ repeated elements})\cdot(K-1)$$
where if $K\leq \lfloor\frac{n}{2}\rfloor$ then,
$$(\text{number of elements of $S_{n}$ with $K$ repeated elements}) = (\text{number of elements of $S_{n-1}$ with $K-1$ repeated element}) + (n-K)$$
Finally, observe that if $K= \lfloor\frac{n}{2}\rfloor$ then $(\text{number of elements of $S_{n}$ with $K$ repeated elements}) = 1$.
I think this should be enough to get your formula.
