2
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ You are not trying to prove that $n! + 1 = (n+1)!$. This equality is not even true. $\endgroup$
    – Pilcrow
    Mar 6, 2022 at 20:29
  • $\begingroup$ Your last step is not clearly formulated. $\endgroup$
    – F_M_
    Mar 6, 2022 at 20:31
  • 1
    $\begingroup$ As N.F. Taussig points out, you need to clearly state the reasoning for the base case (trivial though it may be) $\endgroup$ Mar 6, 2022 at 20:37
  • 2
    $\begingroup$ 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. $\endgroup$ Mar 6, 2022 at 20:42

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .