# 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

• You are not trying to prove that $n! + 1 = (n+1)!$. This equality is not even true. Mar 6, 2022 at 20:29
• Your last step is not clearly formulated.
– F_M_
Mar 6, 2022 at 20:31
• As N.F. Taussig points out, you need to clearly state the reasoning for the base case (trivial though it may be) Mar 6, 2022 at 20:37
• The base case should be an argument for why there are only 1! ways to form a line out of 1 person. "$n=n!\Rightarrow1=1!$" does nothing to that effect. And for the inductive step you should try to prove "If $n$ people can form a line in $n!$ ways, then $n+1$ people can form a line in $(n+1)!$ ways". Which is also not what you were attempting to do. Mar 6, 2022 at 20:42

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$$.

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.

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)!$$

• The base case is also problematic since no argument has been made that there is one way to arrange one person in line. Mar 6, 2022 at 20:29
• @N.F.Taussig Why do you think the statement is not trivial? There is only one unique arrangement of one person. Mar 6, 2022 at 20:32
• Where does Effective Learning say that in his/her proof? Mar 6, 2022 at 20:32
• @N.F.Taussig Oh right I see Mar 6, 2022 at 20:33