Prove by induction that $n$ people can form a line in $n!$ ways Use the principle of induction to prove that for n people in the line there are $n!$ ways to be in the line.
By principle of induction, we start with the base case: Assume that $n = 1$, then $n = n! \implies 1 = 1!$.
Suppose $P(n)$ is true for all $n$. Then by the principle of induction, $P(n)$ should be true for $n+1$ as well.
I am stuck at this step: $(n+1)=(n+1)! \implies n!+1 = (n+1)!$
How can I prove this further? Any help would be appreciated! Thank you
 A: There are a number of flaws in your proof.

*

*You never stated that there is one way to arrange one person in line.

*You cannot assume the result is true for all $n$.  That is what you need to prove. You may assume the result is true for some positive integer $n = m$ once you prove it is true for $n = 1$.

*You have to show that if the result is true for $n = m$, then it must also be true when $n = m + 1$.

Proof. Let $P(n)$ be the statement that the number of ways $n$ people can form a line is $n!$.
Let $n = 1$.  There is one way to arrange a single person in line.  Since $1! = 1$, $P(1)$ holds.
Since $P(1)$ holds, we may assume $P(m)$ holds for some positive integer $m$, which means that there are $m!$ ways for $m$ people to form a line.
Let $n = m + 1$.  We first arrange $m$ of the people in line.  By the induction hypothesis, we can do this in $m!$ ways.  For each arrangement, there are $m + 1$ places where we can introduce the $(m + 1)$st person, the $m - 1$ spaces between successive people in the row of $m$ people and the two ends of the row.  By the Multiplication Principle, there are $(m + 1)m! = (m + 1)!$ ways to arrange $m + 1$ people in line.  Thus, $P(m) \implies P(m + 1)$ for each positive integer $m$.
Since $P(1)$ holds and $P(m) \implies P(m + 1)$ for each positive integer $m$, $P(n)$ holds for each positive integer $n$ by the Principle of Mathematical Induction.$\blacksquare$
Note that if $n = 0$, there are no people to arrange.  There is only one way to arrange no people, namely do nothing.  Since $0! = 1$, $P(0)$ holds.  Hence, we could prove the result for all nonnegative integers $n$.
A: Let $P(n)$ be the number of arrangements of the people. You want to show that $P(n)=n!$.
You can argue as follows. Consider $n+1$ people. Now isolate one of them, call this person $p_0$. Then $n$ people remain, and we can (by induction hypothesis) place then in line in $n!$ ways. To get all $n+1$ people in line, we need to pick a spot for $p_0$. Convince yourself that $p_0$ can be placed in $n+1$ spots. Hence we have the formula
$$
P(n+1) = (n+1)P(n) = (n+1)n! = (n+1)!,
$$
and we are done.
A: Suppose $P(n)$ is true for a fixed $n\geq 1$, i.e. there are $n!$ ways to arrange $n$ people in a line. For each of these arrangements, there are $n+1$ ways to insert the $(n+1)$th person in the line. Thus, the total number of ways to arrange $n+1$ people in the line is $(n+1)\times n!=(n+1)!$
