# How to prove: $n! \times (n+1) = (n+1)!$

Plugging in numbers shows me that it is the same, but I don't know how to get from one to the other.

I get stuck at: $$n!(n+1) = n n! + n!$$ I can't make the connection for the final step.

$(2n + n)!$ doesn't seem right, cause then i would just take n out again and be left with $n!$ $(n+1)$ which is the same thing that I started with...yeah for U turns.

-
Hint: $n!=1\cdot 2\cdot 3\cdot\ldots\cdot(n-1)\cdot n$, and $(n+1)!=1\cdot 2\cdot 3\cdot\ldots\cdot n\cdot(n+1)$ –  no identity Feb 7 '12 at 23:53
You’re much better off not multiplying out to get $nn!+n!$; see @Norbert’s hint instead. –  Brian M. Scott Feb 7 '12 at 23:55
It depends on your definition of the factorial function. I'd define $n!$ by $0!=1$ and $n! = n\cdot (n-1)!$ for $n>0$, which makes the equation true by definition. –  Chris Taylor Feb 8 '12 at 0:00
Similar question: math.stackexchange.com/questions/101644/multiply-factorial –  Matt N. Feb 8 '12 at 7:49
@Chris Taylor: Strongly agree. If we are going to use $1\cdot2\cdots n$ casually, we are really not doing formal induction at all, and again no proof is needed. –  André Nicolas Feb 8 '12 at 9:19

It's almost transparent. $n!=n(n-1)(n-2)\cdots2\cdot1$ and $(n+1)!=(n+1)n(n-1) \cdots2\cdot1$. You should be able to see it from the above. Or you can argue as follows: \eqalign{ \color{maroon}{n!}(n+1)&=[\color{maroon}{n(n-1)(n-2)\cdots2\cdot1 }](n+1)\cr &= (n+1)[\color{maroon}{n(n-1)(n-2)\cdots2\cdot1 }]\cr &=(n+1)\cdot n(n-1)(n-2)\cdots2\cdot1 \cr &=(n+1)!.}

-

Use the definition of factorial. And show the left equals the right rather than the right equals the left.

-

We could use a combinatorial argument to prove that:

$n!(n+1) = (n+1)!$

This may not be what the PO wants, nevertheless, I found it interesting!

is to construct 2 scenarios for generating permutation.

Scenario 1 takes (n+1) objects to permute. The number of permutation is $(n+1)!$ by definition. This covers the right hand side of the equation (see fig.1)

Scenario 2 permutes the (n+1) objects in 2 steps. The first step permutes $n$ objects and in the second step tries to create the final permutation using $(n+1)$ objects. As an example, let $n+1=3$, so $n=2$, and we want to generate permutations for A,B,C (n+1 objects). To do that we'll create 2 sets from {A,B,C}. Namely {A,B} and {C}.

{A,B} can be permuted in $2!=2*1=2$ different ways as in Fig.2, but we are after creating all possible combinations form {A,B,C}, so we need to use C with each of the generated permutations {A,B} and {B,A}.

We can merge C in the permutation A,B for example, in 3 ways (that is n+1 ways), to obtain 3 new permutations,namely: (C, A, B), (A, C, B) and (A, B, C). This merging process can repeat for each row of the $n!$ rows resulting from permuting the $n$ objects.

That is, we end up with $n! *(n+1)$ permutations, which is the left hand side of the equation.

-

Yet another way to write out a "proof" would be using product notation and the definition $n! = \prod_{k=1}^n k$:

$$(n+1)\,n! = (n+1) \prod_{k=1}^n k = \prod_{k=1}^{n+1} k = (n+1)!$$

But of course, as Chris Taylor points out in the comments, the validity of proofs like this really depends on what definition of the factorial you're starting from, and on what lemmas you may take as already proven.

-