this is homework!!
Let $n \geq 1$ be an integer and consider $n$ people $P_1,P_2,\ldots,P_n$. Let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group consists of either one or two people.
Determine $A_1$, $A_2$, and $A_3$.
Prove that for each integer $n \geq 3$, $[ A_n = A_{n-1} + (n-1) \cdot A_{n-2}]$
Ok now, I've determined here I've only been giving a left hand side of the expression as I still need an algebraic eq'n to determine what $A_n$ would be, I can then use induction to prove the eq'n above is this thinking correct?
next, I have sort of figured out what the expression would be equal too but I'm having a hell of a time to create an equation for
$A_k = (1 + _{k}C_{2}(1 + \frac{_{k-2}C_{2}}{2!}(1+\frac{_{k-4}C_{2}}{3!}(1 + ...))))$
my idea here is basically count the number of combinations where there are no goups consisting of 2 ppl, then add that with all combinations with 1 group consisting of 2 ppl (the rest 1), and so forth up to floor(n/2) <- max number of groups consisting of 2 people, yeah some help to point me in the correct direction would be awesome
Edit
im used to induction questions being in the form The function $f : N \rightarrow Z$ is recursively defined as follows: [ \begin{array}{ccl} f(0) & = & 3 , \\ f(n) & = & 2 \cdot f(n-1) - \left( f(n-1) \right)^2 \mbox{ if $n \geq 1$.} \end{array} ] Prove that $f(n) = 1 - 2^{2^n}$ for all integers $n \geq 1$. ($2^{2^n}$ means $2$ to the power of $2^n$.)
and now I would show that $f(k+1) = 2 \cdot f(k) - \left( f(k) \right)^2 = 1 - 2^{2^{k+1}}$ where $n = k+1$
now i have a left and right side of the equation in which I can show each other are equal.
back to the question at hand....
simple stating adding 1 to k on both sides and saying because
$[ A_k = A_{k-1} + (k-1) \cdot A_{k-2}]$, then jumping to
$[ A_{k+1} = A_{k} + (k) \cdot A_{k-1}]$ doesn't feel right to me I haven't shown or proved anything, am I incorrect in this belief?
$n=1$: $P_1$ must be alone, hence $A_1=1$
$n=2$: $P_1$ and $P_2$ are grouped or not, hence $A_2=2$
When you add another, $P_n$, there are two cases:
$P_n$ gets to be alone. Now you have to divide the rest which can be done in $A_{n-1}$ ways.
$P_n$ groups with one of the $n-1$ other people. Now dividing the rest can be done in $A_{n-2}$ ways.
That is $A_n=A_{n-1}+(n-1)\cdot A_{n-2}$
From the above we have $A_3=2+2\cdot1$