背景：
存在一组序列\(A_{nk},n \ge 0, k \ge 0\)，并且该数组满足如下关系：
$$
\require{AMSmath}
\begin{align}
& A_{n0} = 1 \\
& A_{0k} = \delta_{0k} \\
& A_{nk} = A_{(n-1)k}+A_{(n-1)(k-1)} + \binom{n}{k},nk \gt 0
\end{align}
$$
问题：
找到A_{nk}的表达式
解构：
根据已知的通项表达式\(A_{nk} = A_{(n-1)k}+A_{(n-1)(k-1)} + \binom{n}{k}\)，进行递归展开如下：
$$
\begin{align}
A_{nk} &= A_{(n-1)k}+A_{(n-1)(k-1)} + \binom{n}{k} \\
&= A_{(n-2)k}+A_{(n-2)(k-1)} + \binom{n-1}{k} + A_{(n-2)(k-1)} + A_{(n-2)(k-2)} + \binom{n-1}{k-1} + \binom{n}{k} \\
&= A_{(n-2)k}+2A_{(n-2)(k-1)} + A_{(n-2)(k-2)} + \binom{n-1}{k-1}+\binom{n-1}{k}+\binom{n}{k} \\
&= A_{(n-2)k}+2A_{(n-2)(k-1)} + A_{(n-2)(k-2)} +2\binom{n}{k} \\
&= A_{(n-3)k}+A_{(n-3)(k-1)} + 2A_{(n-3)(k-1)} + 2A_{(n-3)(k-2)} + A_{(n-3)(k-2)} + A_{(n-3)(k-3)} + \binom{n-2}{k}+ 2\binom{n-3}{k-1} + \binom{n-2}{k-2} + 2\binom{n}{k} \\
&= A_{(n-3)k}+3A_{(n-3)(k-1)} + 3A_{(n-3)(k-2)} + A_{(n-3)(k-3)} + \binom{n-2}{k}+ 2\binom{n-2}{k-1} + \binom{n-2}{k-2} + 2\binom{n}{k} \\
&= A_{(n-3)k}+3A_{(n-3)(k-1)} + 3A_{(n-3)(k-2)} + A_{(n-3)(k-3)} + \binom{n-2}{k}+ 2\binom{n-2}{k-1} + \binom{n-2}{k-2} + 2\binom{n}{k} \\
&= A_{(n-3)k}+3A_{(n-3)(k-1)} + 3A_{(n-3)(k-2)} + A_{(n-3)(k-3)}+ 3\binom{n}{k} \\
&= \cdots \\
&=\sum_{\lambda=0}^{l} \binom{l}{\lambda}A_{(n-l)(k-\lambda)} + l \binom{n}{k},\quad l \in [1,n] \\
&= \sum_{\lambda=0}^{n} \binom{n}{\lambda} A_{0(k-\lambda)} + n\binom{n}{k} \\
&= (n+1)\binom{n}{k},\quad nk \gt 0
\end{align}
$$
至此，项A_{nk}的表达式得到解构！
发表评论