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

• $x$

• $k$

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

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

Here are the answers to your three cases.

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})$.

StackExchange Computer Science Q#97324, answer score: 3