Trying to compute high order derivatives of a power of a function, WolframAlpha gives me this answer

$$\frac{d^n f(x)^N}{dx^n} = N \binom{n - N}{n} \sum_{k=0}^n \frac{(-1)^k}{N-k} \binom{n}{k} \frac{d^n f(x)^k}{dx^n} f(x)^{N-k}$$

What is $\binom{n-N}{n}$, for $N > n$ ?

If I define $F(N,n) = \frac{d^n f(x)^N}{dx^n}$ the recursion is

$$F(N,n) = N \binom{n - N}{n} \sum_{k=0}^n \frac{(-1)^k}{N-k} \binom{n}{k} F(k, n) f(x)^{N-k}$$

But how can I compute this?

if I take $F(n,n)$ it becomes

$$F(n,n) = n \binom{0}{n} \sum_{k=0}^n \frac{(-1)^k}{n-k} \binom{n}{k} F(k, n) f(x)^{n-k} $$

The term with $k=n$ is problematic, how should I handle, I can take it out of the summation and I get something like this.

$$\left(1 - \frac{n(-1)^n}{0}\right)F(n,n) = n \binom{0}{n} \sum_{k=0}^{n-1} \frac{(-1)^k}{n-k} \binom{n}{k} F(k, n) f(x)^{n-k}$$

The complexity $O(n^2)$ of this recurrence is interesting, but how could I compute this?

It would be preferable if it was an algorithm that could compute $F(N, k)$, one by one using the lower order derivatives of the same power.

  • $\begingroup$ Apparently the identity is only valid for $N>n$, otherwise you would have division by $0$ for $k=n$. As for the binomial with negative numerator, that can be viewed as a natural generalization of standard binomial coefficient, see for example this post $\endgroup$
    – Sil
    Apr 20, 2022 at 19:41
  • $\begingroup$ As for the formula it is hard to tell what you are looking for, the definition of $n$-th derivative is already recursive $\frac{d^n f(x)^N}{dx^n}=\frac{d}{dx}(\frac{d^{n-1} f(x)^N}{dx^{n-1}})$, why not use that? $\endgroup$
    – Sil
    Apr 20, 2022 at 19:45
  • 1
    $\begingroup$ Because I want to use this in a numerical computation, related to this question. I have a truncated series, a polynomial of degree ~10k, and I want the 128th power of it. But in many case I can truncate it to have degree ~16*10k. To compute it faster I am calculating the polynomial product over the ring of polynomials mod $(x^L - 1)$, and I want to determine an $L$ that will be enough so that the wrapped terms have negligible influence on the result. $\endgroup$
    – Bob
    Apr 20, 2022 at 20:16
  • $\begingroup$ I have one solution with complexity $O(n^2 log(N))$ $\endgroup$
    – Bob
    Apr 20, 2022 at 20:19
  • 1
    $\begingroup$ I see, in any way you might want to look at Faà di Bruno's formula for $\frac{d^{n}}{dx^{n}}f(g(x))$. $\endgroup$
    – Sil
    Apr 20, 2022 at 20:55


You must log in to answer this question.

Browse other questions tagged .