Counting the number of different ways in which groups of one or two can be formed... I'm having trouble proving that the number of ways n>3 people can be divided into groups of either one or two is equal to:
$A_n = A_{n-1} + (n-1)⋅A_{n-2} $
I'm trying to prove this by counting but am open to suggestions.
So far, I've got:
The base cases:
$A_1 =1$
$A_2 =2$
$A_3 =4$
And I think that the first part $A_{n-1}$ is just counting all the ways if the $n$th term is added to $A_{n-1}$ on a group by itself.
I also believe that the second term $(n-1)⋅A_{n-2} $ is counting the number of groups of 1 in $A_{n-1}$ that the $n$th term can pair up with, although I don't know how to even start proving this since I can't get the logic behind exactly how it's counting these groups of 1.
I'd really appreciate any guidance on how to go about this...
 A: When you have $n$ people, consider what you do with the last person.
If you let him alone, you have $A_{n-1}$ ways to group the other $n-1$ people.
If you group him with someone else, you have $n-1$ ways to do that. And after that you need to group the other $n-2$ people. That's where comes from $(n-1)A_{n-2}$
A: For such an arrangement for $n$ people, there are two cases: $n$ is by itself or $n$ is paired with someone.
For the first case, if you remove $n$, then it's just an arrangement for $n-1$ people, and so, there are $A_{n-1}$ arrangements where $n$ is by itself.
Moving on to the second case, suppose that $n$ is paired off with $i$. Then, removing $n$ and $i$, it is a valid arrangement for $n-2$ people, and so, there are $A_{n-2}$ arrangements of $n$ being paired off with $i$. Since there are $n-1$ choices for $i$, you get the recursion
$$A_n = A_{n-1} + (n-1)A_{n-2}.$$
A: For future reference here is a derivation using combinatorial species. The species under consideration is 
$$\mathfrak{P}(\mathfrak{P}_{=1}(\mathcal{Z})+\mathfrak{P}_{=2}(\mathcal{Z})).$$
This gives the exponential generating function
$$G(z) = \exp\left(\frac{z}{1!} + \frac{z^2}{2!}\right)
= \exp\left(z+\frac{z^2}{2}\right).$$
Differentiating we have
$$G'(z) = \exp\left(z+\frac{z^2}{2}\right) (1+z)
= G(z) (1+z).$$
Extracting coefficients we obtain
$$n! [z^n] G'(z) = A_{n+1}
= n! [z^n] G(z) (1+z)
= A_n + n! [z^n] z G(z)
\\= A_n + n! [z^{n-1}] G(z)
= A_n + n! \frac{A_{n-1}}{(n-1)!}
= A_n + n A_{n-1}.$$
This finally yields
$$A_{n+1} = A_n + n A_{n-1}$$
which is the result we were trying to prove.
Remark. What we have here is a special case or rather restriction of the species
$$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$
which yields the generating function of the Stirling numbers of the second kind
$$G(z, u) = \exp(u(\exp(z)-1))$$
where
$${n\brace k} = n! [z^n] \frac{(\exp(z)-1)^k}{k!}.$$
