Generating a certain number after $k$ operations. Obtain a formula for this number as a function of $k$ There are n cookies on a table. Adam did this series of steps:
In the 1st step he put 1 cookie in the middle of every two neighbouring cookies, in the 2nd step he put 2 cookies in the middle of every two neighbouring cookies, in the kth step he put k cookies in the middle of every two neighbouring cookies... Find the formula for computing the number of cookies on the table after the kth step.
Now I have found that the formula for it is:
(k+1)!(n-1)+1
However, I got this purely by computing the number of cookies manually for small ks and simply observing the patterns.
How can I prove that this formula works, and why does it work?

*

*Instead of considering previous pairs of cookies, ignore the one on the far right, so you start with $n-1$ cookies 

*and say that at the $k$th step you put $k$ cookies to the immediate right of each previous cookie, in effect multiplying the number of cookies by $k+1$ on the $k$th step

*so from the start you multiply $(n-1)$ by $2,3,4,5,\ldots,k$ and $k+1$, i.e. by $(k+1)!$ to give $(k+1)!\,(n-1)$

*and finally add back the $1$ far right cookie you ignored at the start to give $(k+1)!\,(n-1)+1$
