# Recursion for derivatives of powers

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.

• 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
– Sil
Apr 20, 2022 at 19:41
• 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?
– Sil
Apr 20, 2022 at 19:45
• 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.
– Bob
Apr 20, 2022 at 20:16
• I have one solution with complexity $O(n^2 log(N))$
– Bob
Apr 20, 2022 at 20:19
• 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))$.
– Sil
Apr 20, 2022 at 20:55