1

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?

Jean Marie
  • 81,803
pavle
  • 649
  • By mathematical induction on $k$. Note that the first step is for $k=0$, before Adam did anything. –  Oct 11 '17 at 20:13
  • Yeah ok, i can prove it by induction, but why does the formula work? It is not intuitive to me why it works. @mathguy – pavle Oct 11 '17 at 20:18
  • Fair enough. Can you "see it" (is it intuitive) for the case $n=2$? If the result is true (for WHATEVER reason) for $n=2$, it is easy - and intuitive - to show it is true for $n>2$ also, this time by induction on $n$. –  Oct 11 '17 at 20:23

1 Answers1

2

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

Henry
  • 157,058