# Need proof/explanation for a problem involving factorials

Suppose you have a list of integers from 1 to N

And say you remove any two numbers, X and Y, from the list of numbers, and add (X + Y + X.Y) to the list

If you keep doing this until you have only one number remaining (which means I performed the above operation N-1 times), the answer turns out to be (N+1)! - 1

For example, let N = 4 Which means my list is: {1, 2, 3, 4}

If I choose X = 1 and Y = 2, then (1 + 2 + 1.2) is 5, so my list now becomes {5, 3, 4}

Now let X = 5 and Y = 4, then (5 + 4 + 5.4) is 29, so my list now becomes {29, 3}

And when X = 29 and Y = 3, we get (29 + 3 + 29.3) which is {119}

And 119 turns out to be 5! - 1 So for N = 4, my answer is 5!-1

Similarly for any N, my result ends up being (N+1)! - 1

Can someone provide some proof or explanation for this?

For reference, my question is based on this problem- https://www.codechef.com/MAY19B/problems/REDONE

• May 25 '19 at 16:20
• @MartinR Thank you and sorry. I should have searched the site much more thoroughly, my bad. May 25 '19 at 16:24

Suppose your list is $$L$$. Then consider $$I=\prod\limits_{i\in L}(i+1)$$. $$I$$ is invariant, since when you do one of your operations, $$x,y\to x+y+xy$$, $$(x+1)(y+1)=x+y+xy+1$$ so $$L$$ remains constant. Thus $$L_{\text{start}}=L_{\text{end}}$$, so since $$L_{\text{start}}=(n+1)!$$, we must have $$L_{\text{end}}=(n+1)!$$ But there's just one number left so this number must be $$(n+1)!-1$$.