[A-L] (2023/24) Foglio 1 - Esercizio 9

[Elia-Belli]

[gpelisset]

Per semplicita' pongo $p_N := p_N(k), C_1 := C_1(k)$

Per dimostrare l'uguaglianza calcolo
$$\dfrac{p_N - \dfrac{C_1}{N}}{\dfrac{1}{N} }$$
e mostro che questo oggetto per $N \to +\infty$ tende a zero per un opportuno $C_1$.

Allora vale
$$\dfrac{p_N - \dfrac{C_1}{N}}{\dfrac{1}{N}} = p_N N - C_1 = \dfrac{N^k - N(N-1)...(N-k+1)}{N^{k- 1}} - C_1 = \dfrac{{\sum_{j = 1}}^{k - 1} j N^{k-1} + o(N^{k - 2})}{N^{k- 1}} - C_1 = \dfrac{k(k-1)}{2} - C_1 + o(1)$$
Affinche' il limite per $N \to \infty$ sia 0, $C_1 = \dfrac{k(k-1)}{2}$
2)
Ripeto lo stesso ragionamento,
$$\dfrac{p_N - \dfrac{C_1}{N} - \dfrac{C_2}{N^2}}{\dfrac{1}{N^2}} = N^2 p_N - N C_1 - C_2 = \dfrac{N^k - N(N-1)...(N-k+1)}{N^{k- 2}} - \dfrac{N k(k - 1)}{2} - C_2 = \dfrac{N^k - N(N-1)...(N-k+1) - N^{k-1} k(k-1)/2 - C_2 N^{k-2}}{N^{k- 2}} = \dfrac{o(N^{k-2}) - N^{k-2} \sum_{1 \le i < j \le k-1}ij - C_2 N^{k-2}}{N^{k- 2}}$$
Da cio' segue che
$$C_2 = -\sum_{1 \le i < j \le k-1}ij = -\sum_{i = 1}^{k-2} i (\sum_{j = i}^{k - 1} j) = -\sum_{i = 1}^{k-2} i (\sum_{j = 1}^{k - 1} j - \sum_{j = 1}^{i} j) = -\sum_{i = 1}^{k-2} \dfrac{i ( (k-1)k- i (i + 1))}{2} = -\dfrac{k(k-1)^2(k-2)}{4} + \dfrac{1}{2}\sum_{i = 1}^{k-2} i i (i +1)) = -\dfrac{k(k-1)^2(k-2)}{4} +\dfrac{(k-1)^2(k-2)^2/4 + (k-2)(k-1)(2k-3)/6}{2} = -\dfrac{(k-1)(k-2)}{24}(6k(k-1) - 3(k-1)(k-2) - 2(2k-3)) = -\dfrac{(k-1)(k-2)}{24}(3k^2 - k )$$

[gpelisset]

La correttezza dei conti e' data dal seguente programma

from sympy import *

n = symbols('n')
k = 20
expr = n - prod([n - i for i in range(k)]) / (n ** (k - 1))
print("C_1 =", limit(expr, n, oo))
print("exepected =", (k - 1) * k / 2)

expr = n**2 - prod([n - i for i in range(k)]) / (n ** (k - 2)) - k * (k - 1) / 2 * n
print("C_2 =", limit(expr, n, oo))
print("expected =", - (k - 1)*(k - 2) * (3 * k ** 2 - k) / 24)