encontrar una fórmula explícita para una recursión de dos variables

Question

Mi objetivo es encontrar una fórmula explícita para un definidos de forma recursiva funtion $f_{k,N}:\{1,\ldots,N\} \to \mathbb R$ donde $N,k \in \mathbb N$.

(Si importa. $f_{k,N}$ es una función de distribución de probabilidad sobre $\{1,2,\ldots,N\}$)

Pero yo no tengo ni idea de cómo abordar este problema.

Las anclas son:

$$f_{k,1}(1) = 1 \: \forall\, k$$

$$f_{1,N}(x) = \frac 1 N \: \forall N \in \mathbb N, x \in \{1,2,\ldots,N\}$$

La recursividad es:

$$f_{k,N}(x) = \sum_{l=x}^N \frac{1}{l} f_{k-1,l}(x) $$

Existe un enfoque general para este problema? ¿Cualquier persona puede encontrar un no-recursiva fórmula para $f_{k,N}$ en general, o al menos en algunos casos especiales?

---

EDIT: En el entretanto, yo era capaz de llegar con el seguimiento a casos especiales, pero podemos encontrar una fórmula general para el $x \in \{1,2,\ldots,N\}$?

$$ f_{k,N}(N) = \frac{1}{N}f_{k-1,N}(N) = \ldots = \frac{1}{N^{k-1}} f_{1,N}(N) = \frac{1}{N^k} $$

$$ \begin{align} f_{k,N}(N-1) &= \frac{1}{N-1} \underbrace{f_{k-1,N-1}(N-1)}_{= \frac{1}{(N-1)^{k-1}}}+ \frac{1}{N} f_{k-1,N}(N-1) \\ &= \frac{1}{(N-1)^k} + \frac{1}{N}\left( \frac{1}{(N-1)^{k-1}} + \frac{1}{N}f_{k-2,N}(N-1) \right)\\ &= \ldots = \sum_{n=0}^k \frac{1}{N^{k-n}(N-1)^n} \end{align} $$

Answer 1

Si $f_{k, n}(x)$ por cada $1 \leq x \leq n$ forma un vector $\vec{f_{k, n}}$ de probalities, entonces:

$$\vec{f_{k+1, n}} = \begin{bmatrix} 1 & 1\over 2 & 1\over 3 & \cdots & 1\over n \\ 0 & 1\over 2 & 1\over 3 & \cdots & 1\over n \\ 0 & 0 & 1\over 3 & \cdots & 1\over n \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ 0 & 0 & 0 & \cdots& 1\over n \end{bmatrix} \vec{f_{k, n}} = A_n\vec{f_{k, n}}$$

Podemos usar esta identidad repetidamente para mostrar que:

$$\vec{f_{k, n}} = A_n^k \begin{bmatrix}0\\ \vdots \\ 0 \\ 1\end{bmatrix}$$

Podemos usar $A$'s vectores propios y valores a diagonalize $A$ tal que $P^{-1}HP = A$ donde $H$ es una matriz diagonal. Esto es beneficioso, porque entonces tenemos $A^k = P^{-1} H^k P$, y tomando el poder de una matriz diagonal es trivial.

Desde $A$'s elementos de la diagonal son todos distintos de su diagonal es también de sus valores propios. Pero como resulta que, los vectores propios de a $A$ forma de triángulo de Pascal! E. g. para $n = 5$:

$$P^{-1} = \begin{bmatrix} 1 & -1 & 1 & -1 & 1 \\ 0 & 1 & -2 & 3 & -4 \\ 0 & 0 & 1 & -3 & 6 \\ 0 & 0 & 0 & 1 & -4 \\ 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}, P = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 & 4 \\ 0 & 0 & 1 & 3 & 6 \\ 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} $$

El uso de este conocimiento se puede construir una fórmula explícita para $f_{k, n}$:

$$f_{k,n}(x) = \sum_{l=1}^n \underbrace{(-1)^{x + l}\binom{l-1}{x-1}}_\text{$x$th row of $P^{-1}$} \overbrace{\frac{1}{l^k}}^\text{$H$ diagonal}\underbrace{\binom{n-1}{l-1}}_\text{last column of $P$}$$

El uso de binomio de identidades y darse cuenta de que la suma es cero para $l < x$ podemos simplificar esto:

$$f_{k, n}(x) = \frac{x}{n} \left | \sum_{l=x}^n \frac{(-1)^l}{l^k}\binom{l}{x}\binom{n}{l} \right |$$

Answer 2

Dejar $g_{k,n}(x)=\frac1nf_{k,n}(x)$. Luego$$ g_{k,1}(1)=1$ $$$g_{1,N}(x)=1\text{ for }1\le x\le N $ $$$g_{k,N}(x)=\frac1N\sum_{l=x}^Ng_{k-1,l}(x) $ $ Primero observe que$g_{k,N}(x)=0$ para$x>N$. Henec la recursión se puede simplificar (?) A$$g_{k,N}(x)=\frac1N\sum_{l=1}^Ng_{k-1,l}(x). $ $ A partir de esto, uno puede mostrar fácilmente algunas cosas como$\lim_{k\to\infty}g_{k,n}(x)=1$