## Task 6B - 221246B

In the investigation of frequency distributions in mathematical statistics, functions appear that are defined for finitely many natural numbers and are required to satisfy so-called functional equations (equations between different function values).

An example of this is the following:

Given a natural number $n \geq 2$ and a real number $p$ with $0<p<1$.

Determine (in dependence on $n$ and $p$) those functions $f$ with the set $\{1,2, \ldots, n\}$ as the domain, which for $k=1,2, \ldots, n$ satisfy the following equation (1):

$$
\sum_{x=0}^{n} x \cdot(x-1) \cdot(x-2) \cdot \ldots \cdot(x-k+1) \cdot f(x)=n \cdot(n-1) \cdot(n-2) \cdot \ldots \cdot(n-k+1) \cdot p^{k}
$$

Hint: For $k=1$, equation (1) is to be interpreted as

$$
\sum_{x=0}^{n} x \cdot f(x)=n \cdot p
$$
Simplified, one can write:

$$
\sum_{x=0}^{n} \frac{x!}{(x-k)!} f(x)=\frac{n!}{(n-k)!} p^{k}
$$

We divide both sides by $k!$:

$$
\sum_{x=0}^{n}\binom{x}{k} f(x)=\binom{n}{k} p^{k}
$$

Since $\binom{a}{b}=0$ for $a<b$, the index $x$ can also start at $k$, because the summands for $x<k$ would all be zero:

$$
\sum_{x=k}^{n}\binom{x}{k} f(x)=\binom{n}{k} p^{k}
$$

This means that a linear system of equations for the $f(x)$ is present, which has a triangular form. For $k=n$, the equation is simply

$$
f(n)=p^{n}
$$

One can then recursively compute the values for $f(k)$ from $f(k+1) \ldots f(n)$. Performing this manually for a small $n$, e.g., $n=3$, reveals a pattern. It seems to hold that:

$$
f(x)=\binom{n}{x} p^{x}(1-p)^{n-x}
$$

We attempt to prove the validity of this formula by substituting it into (2):

$$
\begin{gathered}
\sum_{x=k}^{n}\binom{x}{k}\binom{n}{x} p^{x}(1-p)^{n-x}=\binom{n}{k} p^{k} \\
\sum_{x=k}^{n} \frac{x!}{k!(x-k)!} \cdot \frac{n!}{x!(n-x)!} p^{x}(1-p)^{n-x}=\binom{n}{k} p^{k} \\
\sum_{x=k}^{n} \frac{n!}{k!(n-x)!(x-k)!} p^{x}(1-p)^{n-x}=\binom{n}{k} p^{k}
\end{gathered}
$$

Terms that do not contain $x$ can be factored out of the sum:

$$
\frac{n!}{k!} \sum_{x=k}^{n} \frac{1}{(n-x)!(x-k)!} p^{x}(1-p)^{n-x}=\binom{n}{k} p^{k}
$$

We divide by $\binom{n}{k}$:

$$
\begin{gathered}
(n-k)!\sum_{x=k}^{n} \frac{1}{(n-x)!(x-k)!} p^{x}(1-p)^{n-x}=p^{k} \\
\sum_{x=k}^{n}\binom{n-k}{x-k} p^{x}(1-p)^{n-x}=p^{k}
\end{gathered}
$$

We substitute $x=k+m$ with $m=0 \ldots(n-k)$:

$$
\sum_{m=0}^{n-k}\binom{n-k}{m} p^{k+m}(1-p)^{n-k-m}=p^{k}
$$

We divide by $p^{k}$ once more:

$$
\sum_{m=0}^{n-k}\binom{n-k}{m} p^{m}(1-p)^{n-k-m}=1
$$

The left side corresponds to the binomial theorem, since

$$
\sum_{m=0}^{n-k}\binom{n-k}{m} p^{m}(1-p)^{n-k-m}=(p+(1-p))^{n-k}=1^{n-k}=1
$$

Therefore, equation (2) is indeed satisfied, and the desired function is given by the formula in (3).