# Solving $$f(x, k) = f(x, k-1) + f(x-1, k-1) + \dots + f(1, k-1)$$ in terms of $x$

I'm having trouble determining the complexity of an algorithm. Let's say the number of operations of my algorithm is described by $$f(x, k) = f(x, k-1) + f(x-1, k-1) + f(x-2, k-1) + \dots + f(1, k-1)$$ where $f(x, 1) = x$

How can I describe the growth of $f(x)$ in terms of

1. $x$
2. $k$
3. $x$ when $k=x-1$

For 1), I believe $f(x, k)$ would be exponential in $x$ as $k$ can be taken to be a constant which would reduce the above equation to being similar to

$$f(x) = f(x-1) + f(x-2) + \dots + f(1)$$

Similarly, for 2), I believe $f(x, k)$ would be exponential in $k$ as I would need to take $x$ as a constant which would lead to the below equation

$$f(k) = xf(k-1)$$

Need help with 3) and also validating my thinking for 1) and 2)

• I dont see when the recursion ends. f(x,2)=f(x,1)+f(x-1,2)=x+(f(x-1,1)+f(x-2,2)) = x + (x-1) + (f(x-2,1)+f(x-3,2)) .. Sep 14, 2018 at 18:32
– nave
Sep 15, 2018 at 0:23
• The above equation can be written as $f(x, k) = f(x, k-1) + f(x-1, k)$. Does that give any clues? May be generating functions could solve this? You perhaps need a boundary condition as well ($f(0, k)$ = something) to solve this. Sep 15, 2018 at 4:12
• I had initially written this as $f(x,k)$=$f(x,k−1)$+$f(x−1,k)$ in my question as well, but as @RandomPerfectHashFunction pointed out, this recurrence does not end as there is always a term with $f(x, k)$ .... So it seems the 2 equations are actually not equivalent given there is only a base case for $f(x,1)$
– nave
Sep 16, 2018 at 22:09

You can write your recursion as $$\begin{split} f(x,k) &= \sum\limits_{i_1=1}^x f(i_1,k-1)\\ &= \sum\limits_{i_1=1}^x \sum\limits_{i_2=1}^{i_1} f(i_2,k-2)\\ &= \vdots \\ &= \sum\limits_{i_1=1}^x \sum\limits_{i_2=1}^{i_1} \ldots \sum\limits_{i_{k-1}=1}^{i_{k-2}} f(i_{k-1},1)\\ &= \sum\limits_{i_1=1}^x \sum\limits_{i_2=1}^{i_1} \ldots \sum\limits_{i_{k-1}=1}^{i_{k-2}} i_{k-1}\\ \end{split}$$ We know that from Faulhaber's formula $$\sum\limits_{i_{k-1}=1}^{i_{k-2}} i_{k-1} = \frac{1}{2}O(i_{k-2}^2)$$ So $$f(x,k) = \sum\limits_{i_1=1}^x \sum\limits_{i_2=1}^{i_1} \ldots \sum\limits_{i_{k-2}=1}^{i_{k-3}} \frac{1}{2}O(i_{k-2}^2)$$ Also $$\sum\limits_{i_{k-2}=1}^{i_{k-3}} O(i_{k-2}^2) = \frac{1}{3}O(i_{k-3}^3)$$ If you keep doing this, you'd get $$f(x,k) = \frac{1}{2 \times 3 \times 4 \times \ldots \times (k-1) } \sum\limits_{i_1=1}^x O(i_1^{k-1}) = \frac{1}{2 \times 3 \times 4 \times \ldots \times (k-1) \times k} O(x^k) = \frac{1}{k!} O(x^k)$$

The answers to all three questions become easier once we proved the following formula for all positive integer $k$ and $x$. $$f(x,k) = \frac{x(x+1)(x+2)\cdots(x+k-1)}{k!}$$ Proof: The formula is easily seen to be true for $k=1$ and all positive integer $x$.

Assume the formula is true for some positive integer $k$ and all positive integer $x$. Then, \begin{align} &f(x, k+1)\\ &=f(x, k) + f(x-1, k) + f(x-2, k) + \dots + f(1, k)\\ &=\frac1{k!}(x(x+1)(x+2)\cdots(x+k-1) + (x-1)x(x+1)(x+2)\cdots(x+k-2)\\ &\quad\quad+\cdots+1\cdot2\cdots k\\ &=\frac1{k!}\left(\frac{x(x+1)(x+2)\cdots(x+k)-(x-1)x(x+1)\cdots(x+k-1)}{k+1}\right.\\ &\quad\quad+\frac{(x-1)x(x+1)\cdots(x+k-1)-(x-2)(x-1)x\cdots(x+k-2)}{k+1}\\ &\quad\quad+\cdots\\ &\quad\quad+\frac{2\cdot3\cdots(k+1)-1\cdot2\cdots k}{k+1}\\ &\quad\quad+\left.\frac{1\cdot2\cdots k}{k+1}\right)\\ &=\frac1{k!}\frac{x(x+1)(x+2)\cdots(x+k)}{k+1}\\ &=\frac{x(x+1)(x+2)\cdots(x+(k+1)-1)}{(k+1)!}\end{align}

By mathematical induction on $k$, the formula is true for all positive integer $k$ and $x$.

1) For fixed $k$ and $x\to\infty$, $$f(x,k)=\frac{x^k}{k!}\frac xx\frac{x+1}x\cdots\frac{x+k-1}{x}\sim\frac{x^k}{k!}$$ That is, $f(x,k)=\Omega(x^k)$.

2) For fixed $x$ and $k\to\infty$, by Stirling's approximation, \begin{align}f(x,k)&=\frac{(x-1+k)!}{(x-1)!k!}\\ &\sim\frac1{(x-1)!}\frac{\sqrt{2\pi(x-1+k)}\left(\frac{x-1+k}{e}\right)^{x-1+k}}{\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}}\\ &=\frac1{(x-1)!}\sqrt\frac{x-1+k}k (x-1+k)^{x-1}\left(\frac{x-1+k}{k}\right)^k\frac{1}{e^{x-1}}\\ &=\frac1{(x-1)!}\sqrt\frac{x-1+k}k\left(\frac{x-1+k}{k}\right)^{x-1}k^{x-1}\left(1+\frac{1}{\frac k{x-1}}\right)^{\frac k{x-1}(x-1)}\frac{1}{e^{x-1}}\\ &\sim\frac1{(x-1)!}k^{x-1}e^{x-1}\frac{1}{e^{x-1}}\\ &=\frac{k^{x-1}}{(x-1)!}\end{align} That is, $f(x,k)=\Omega(k^{x-1})$

3) Let $k=x-1$ go to infinity, again by Stirling's approximation, $$f(x,k) = \frac{(2k)!}{k!k!}\sim \frac{\sqrt{2\pi2k}\left(\frac{2k}{e}\right)^{2k}}{\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}}=\frac{2^{2k}}{\sqrt{\pi k}}$$ That is, $f(k+1,k)=\Omega(k^{-1/2}2^{2k})$.

• a few questions ... 1) How did you come up with the initial formula for $f(x, k)$ which you proved? 2) For fixed $k$ part, why do we need to divide by $x$ raised to power of $k$? 3) For fixed $x$ part, could you please elaborate on going from the second term to the third term and from the third term to the fourth term?
– nave
Sep 16, 2018 at 22:14
• 1) By the recurrence relation we can compute to obtain $f(x,1)=x$ and $f(x,2)=n(n+1)/2$ and $f(x,3)=n(n+1)(n+2)/3$. Then observe the pattern. 2) If $k$ is fixed, then $x\sim x, (x+1)\sim x, \cdots, (x+k-1)\sim x$ when $x\to \infty$. So you have a product of $k$ $x$'s. 3) I will update the answer. Sep 16, 2018 at 22:16

For $k \geq 1$, define $$T_k(z) = \sum_{n=0}^\infty f(n,k) z^n,$$ where we define $f(0,k) = 0$ (which agrees with the definition for $k=1$).

Since $f(n,1) = n$ for all $n$, we get $$T_1(z) = \sum_{n=0}^\infty nz^n = z\sum_{n=0}^\infty nz^{n-1} = z \frac{d}{dz} \sum_{n=0}^\infty z^n = z \frac{d}{dz} \frac{1}{1-z} = \frac{z}{(1-z)^2}.$$ For $k > 1$, we have $$T_k(z) = \sum_{n=0}^\infty f(n,k)z^n = \sum_{n=0}^\infty \sum_{m=0}^n f(m,k-1) z^n = \sum_{m=0}^\infty f(m,k-1) \sum_{n=m}^\infty z^n = \\ \sum_{m=0}^\infty f(m,k-1) z^m \sum_{n=0}^\infty z^n = \sum_{m=0}^\infty f(m,k-1) \frac{z^m}{1-z} = \frac{T_{k-1}(z)}{1-z}.$$ A short induction shows that $$T_k(z) = \frac{z}{(1-z)^{k+1}}.$$ You can now consider the bivariate generating function $$S(z,w) = \sum_{n=0}^\infty \sum_{k=1}^\infty f(n,k) z^n w^k = \sum_{k=1}^\infty w^k T_k(z) = z \sum_{k=1}^\infty w^k (1-z)^{-k-1} = \\ \frac{z}{1-z} \sum_{k=1}^\infty \left(\frac{w}{1-z}\right)^k = \frac{zw}{(1-z)^2}\frac{1}{1-w/(1-z)} = \frac{zw}{(1-z)(1-z-w)}.$$ From here you can in principle deduce all asymptotic properties. It is also easy to extract the exact formula, since the coefficients of $\frac{1}{(1-z)^k}$ are known.