-1

I encountered such a recurrence relation:

$$ f(n, k) = k f(n - 1, k) + f(n - 1, k - 1), \text{for } 1 \lt n, 1 \le k \le n \\ f(1,1) = 1 \\ f(1,k) = 0, \text{for } k \ne 1 $$

This looks like a binomial expansion recurrence, but with an extra $k$ in one term.

I wonder if there's a closed form solution for it, or how to simplify it if possible. I have tried to expand out a few terms without obvious pattern.

Rui Liu
  • 567
  • You have $f(1,k)$. It looks like $f(2,1)$ needs a value for $f(1,0)$ to apply recursion. Is it zero? – hardmath Jun 21 '21 at 00:18
  • Assuming it extends to non-positive values, you can get $f(2, 1) = f(1, 1) + f(1, 0) = 1 + 0 = 1$. – ConMan Jun 21 '21 at 00:25
  • Although you do also have to assume that the recurrence relation actually holds for all natural $n$ and $k$ otherwise you technically can't do anything useful. – ConMan Jun 21 '21 at 00:34

1 Answers1

0

This might be useful to get you started:

First, assuming that the recurrence relation should actually apply to all $n, k \in \mathbb{N_0}$, we can show that $f(n, k) = 0$ when $k > n$. And if we add the condition that $f(n, 0) = 0$ then we can prove that $f(n, 1) = f(n, n) = 1$ via some quick induction.

Next, to make some stuff neater later on, let's shift the function to get rid of all the zero values by defining $F(n, k) := f(n - k + 1, k)$. Doing that (and using our above deductions), the defining equations become:

$$F(n, k) = \begin{cases} 1 & n = 1 \mbox{ or } k = 1 \\ kF(n - 1, k) + F(n-1, k-1) & n, k \geq 2 \end{cases}$$

I'll leave you to prove that all of that works.

Next, you can look for some patterns by following fixed values of either $n$ or $k$. For example, look at what happens when $k = 2$:

$$\begin{eqnarray} F(1, 2) & = & 1 \\ F(2, 2) & = & 2 \times 1 + 1 \\ F(3, 2) & = & 2 \times (2 \times 1 + 1) + 1 & = & 2^2 + 2 + 1 \\ F(4, 2) & = & 2 \times (2^2 + 2 + 1) + 1 & = & 2^3 + 2^2 + 2 + 1 \end{eqnarray}$$

This is a pretty standard geometric series, so we can show that $F(n, 2) = 2^n - 1$. Great, that's one closed form down, infinity to go.

Next, try $k = 3$, making use of our newly found closed form for $F(n, 2)$:

$$\begin{eqnarray} F(1, 3) & = & 1 \\ F(2, 3) & = & 3 \times 1 + 2^2 - 1 \\ F(3, 3) & = & 3 \times (3 + 2^2 - 1) + 2^3 - 1 & = & 3^2 + 3 \times 2^2 + 2^3 - 3 - 1 \\ F(4, 3) & = & 3 \times (3^2 + 3 \times 2^2 + 2^3 - 3 - 1) + 2^4 - 1 \\ & = & 3^3 + 3^2 \times 2^2 + 3 \times 2^4 - 3^2 - 3 - 1 \end{eqnarray}$$

And more generally we can write $F(n, 3) = 3^{n - 1} + (3^{n - 2} 2^2 + \ldots + 2^n) - (3^{n - 2} + \ldots + 1)$. Notice that both the bracketed terms are geometric series, so you can find closed form expressions for both of those, and then simplify everything.

When you do that, you should notice that $F(n, 3) = a 3^n + b 2^n + c$ for some values of $a, b, c$. Hopefully that will motivate a more general closed form, but I'll leave the proof of it to you.

ConMan
  • 24,300