Chủ đề này có 2 trả lời

[nhungvienkimcuong]

Kí hiệu $S$ là tập hợp các bộ số nguyên dương có tổng là $2022$. Ví dụ

$$t_1=(2022),\ t_2=(1,1,2020),\ t_3=(1,2021)\ \text{và}\ t_4=(2021,1)$$

là các phần tử phân biệt của $S$. Với mỗi bộ $t$, kí hiệu $p(t)$ là tích các phần tử của $t$. Ví dụ $p(t_1)=2022,\ p(t_2)=2020$ và $p(t_3)=p(t_4)=2021$. Tính tổng
$$\sum_{t\in S}p(t).$$

[perfectstrong]

Ký hiệu $S(n)$ là tập các bộ số nguyên dương có tổng bằng $n$, và $A(n)$ là tổng cần tìm. Ta sẽ tìm cách tính $A(n+1)$ bằng truy hồi.

Trước hết, ta xem xét cách tạo ra $S(n+1)$. Lấy một bộ số $(a_1, a_2, \ldots, a_k)$ bất kỳ từ $S(n+1)$, thì bộ số $(a_2, \ldots, a_k) \in S(n+1-a_1)$.

Do đó:\[A\left( {n + 1} \right) = \sum\limits_{k = 1}^{n + 1} {k \times A\left( {n + 1 - k} \right)} \]

Trong đó, ta quy ước rằng $A(0) = 1$.

Ta kiểm nghiệm lại một vài số hạng đầu tiên:

\[\begin{align*}
A\left( 0 \right) &= 1\\
A\left( 1 \right) &= 1\\
A\left( 2 \right) &= 1A\left( 1 \right) + 2A\left( 0 \right) = 3 = 1.1 + 2\\
A\left( 3 \right) &= 1A\left( 2 \right) + 2A\left( 1 \right) + 3A\left( 0 \right) = 8 = 1.1.1 + 1.2 + 2.1 + 3\\
A\left( 4 \right) &= 1A\left( 3 \right) + 2A\left( 2 \right) + 3A\left( 1 \right) + 4A\left( 0 \right) = 21\\
& = 1.1.1.1 + 1.1.2 + 1.2.1 + 2.1.1 + 1.3 + 3.1 + 2.2 + 4\\
A\left( 5 \right) &= 55\\
A\left( 6 \right) &= 144\\
A\left( 7 \right) &= 377\\
A\left( 8 \right) &= 987\\
A\left( 9 \right) &= 2584\\
A\left( {10} \right) & = 6765
\end{align*}\]

 

Một chút lanh trí sẽ thấy ngay $A(n)=F_{2n} \, \forall n \ge 1$ với $F_n$ là dãy số Fibonacci Do đó, \[A\left( {2022} \right) = {F_{4044}} \approx {6,26.10^{844}}\]

[hxthanh]

Bài này dùng tính toán với tổng thuần tuý thì sẽ như thế này:

Bổ đề

Với các số nguyên dương $r\le n$, ta có
$\sum_{k_1+…+k_r=n} k_1…k_r={n+r-1\choose n-r}$

Có thể dùng quy nạp theo $r$ để chứng minh.
(@Nesbit ơi có thể trích dẫn định lý từ thread khác không?)
Do đó bài toán sẽ trở thành tính tổng thuần tuý:
$$\sum_{r=1}^{2022}\sum_{k_1+…+k_r=2022}k_1…k_r$$
Theo kết quả của @perfectstrong và Theorem thì ta có:

Hệ quả

$\sum_{r=1}^n {n+r-1\choose n-r}=F_{2n}$
trong đó $F_n$ là số Fibonacci thứ $n$