1

Let's start with the monomial $x$. The goal is to get to a constant term by differentiation and multiplication with $2x$. For some $n \in \mathbb{N}$, you have an exact number of steps $k = 2n+1$ you have to take to get there.

For example, for $n = 0$ (3 steps), we have the following paths: $$ x \rightarrow 1 \rightarrow 2x \rightarrow 2 \\ x \rightarrow 2x^2 \rightarrow 4x \rightarrow 4 $$

Similarly, for $n = 2$ (7 steps), we have these possible paths: $$ x \rightarrow 1 \rightarrow 2x \rightarrow 2 \rightarrow 4x \rightarrow 4 \rightarrow 8x \rightarrow 8 \\ x \rightarrow 1 \rightarrow 2x \rightarrow 2 \rightarrow 4x \rightarrow 8x^2 \rightarrow 16x \rightarrow 16 \\ x \rightarrow 1 \rightarrow 2x \rightarrow 4x^2 \rightarrow 8x \rightarrow 8 \rightarrow 16x \rightarrow 16 \\ x \rightarrow 1 \rightarrow 2x \rightarrow 4x^2 \rightarrow 8x \rightarrow 16x^2 \rightarrow 32x \rightarrow 32 \\ x \rightarrow 1 \rightarrow 2x \rightarrow 4x^2 \rightarrow 8x^3 \rightarrow 24x^2 \rightarrow 48x \rightarrow 48 \\ x \rightarrow 2x^2 \rightarrow 4x \rightarrow 4 \rightarrow 8x \rightarrow 8 \rightarrow 16x \rightarrow 16 \\ x \rightarrow 2x^2 \rightarrow 4x \rightarrow 4 \rightarrow 8x \rightarrow 16x^2 \rightarrow 32x \rightarrow 32 \\ x \rightarrow 2x^2 \rightarrow 4x \rightarrow 8x^2 \rightarrow 16x \rightarrow 16 \rightarrow 32x \rightarrow 32 \\ x \rightarrow 2x^2 \rightarrow 4x \rightarrow 8x^2 \rightarrow 16x \rightarrow 32x^2 \rightarrow 64x \rightarrow 64 \\ x \rightarrow 2x^2 \rightarrow 4x \rightarrow 8x^2 \rightarrow 16x^3 \rightarrow 48x^2 \rightarrow 96x \rightarrow 96 \\ x \rightarrow 2x^2 \rightarrow 4x^3 \rightarrow 12x^2 \rightarrow 24x \rightarrow 24 \rightarrow 48x \rightarrow 48 \\ x \rightarrow 2x^2 \rightarrow 4x^3 \rightarrow 12x^2 \rightarrow 24x \rightarrow 48x^2 \rightarrow 96x \rightarrow 96 \\ x \rightarrow 2x^2 \rightarrow 4x^3 \rightarrow 12x^2 \rightarrow 24x^3 \rightarrow 72x^2 \rightarrow 144x \rightarrow 144 \\ x \rightarrow 2x^2 \rightarrow 4x^3 \rightarrow 8x^4 \rightarrow 32x^3 \rightarrow 96x^2 \rightarrow 192x \rightarrow 192 $$

Now I want to know: What is the sum of the results? In the first case, it would be $2+4 = 6$. In the second, it is $$ 8+16+16+32+48+16+32+32+64+96+48+96+144+192 = 840 $$

Through my testing, it seems like the answer is probably $(2n+3)!/(n+1)!$ (it definitely fits with the examples, because $3!/1! = 6/1 = 6$ and $7!/3! = 5040/6 = 840$). But I cannot figure out how to prove it. Is there a nice way?

fynsta
  • 132
  • 6
  • Could you give an example with $n=1$? – MJD Dec 15 '21 at 18:21
  • I don't understand. In your first derivation, you arrive at a constant term straight away ($1$) but the process doesn't terminate – FShrike Dec 15 '21 at 19:18
  • @FShrike yes, but for n=0 we want 4*0+3 = 3 steps – fynsta Dec 15 '21 at 20:24
  • @MJD added a further example. I hope it becomes a little bit clearer now. – fynsta Dec 15 '21 at 20:38
  • I see now. You have pairs $\langle a, b\rangle$, and in one step you can change $\langle a, b\rangle$ to either $\langle 2a, b+1\rangle$ or $\langle ab, b-1\rangle$. For a given $k$, you want to find paths from $\langle 1, 1\rangle$ to $\langle c, 0\rangle$ and you want the sum of all the terminal $c$ values for each possible path of $k$ steps, for some given $k$ which happens to be of the form $4n+3$. – MJD Dec 15 '21 at 22:22
  • @MJD Right, that seems like a better way to formulate it :D – fynsta Dec 15 '21 at 22:36
  • @fynsta why do you exclude k=5, 3 differentiations and 2 multiplications? E.g. $$x \rightarrow 2x^2 \rightarrow 4x^3 \rightarrow 12x ^2\rightarrow 24x\rightarrow24\x \rightarrow 2x^2 \rightarrow 4x \rightarrow8x^2 \rightarrow16x \rightarrow16\\ldots$$ – miracle173 Dec 15 '21 at 22:42
  • @miracle173 This problem is an extension of another problem where that had to be excluded. But feel free to enlarge the scope of the question to k=4n+1 (I guess the results are the same?) I edited the question – fynsta Dec 16 '21 at 08:33

0 Answers0