|
mzhang2021
数列 $s = \{1, 2, 4, 8, 13, 20, 28, 215, 757, 2186\}$. 初始递推为空 $c = \{\}$.
让我们从处理 $i = 0$ 开始。我们有 $c(0) = 0 \neq 1 = s_0$（回想一下，如果递推 $c$ 为空，则 $c(i) = 0$）。嗯，那是不对的。由于这是我们第一次初始化 $c$，设 $c = \{1\}$。
接下来处理 $i = 1$。我们有 $c(1) = c_1 \cdot s_{1-1} = 1 \cdot 1 = 1 \neq 2 = s_1$。不幸的是递归关系是错误的，我们必须调整。对此有一个简单的修复：改为 $c = \{2\}$。现在，$c(1) = 2 \cdot 1 = 2$ 就像我们想要的那样。
接下来，我们处理 $i = 2$。我们有 $c(2) = c_1 \cdot s_{2-1} = 2 \cdot 2 = 4 = s_2$。看起来我们的 $c$ 有效，所以没有必要修改它。
接下来，$i = 3$。$c(3) = c_1 \cdot s_{3-1} = 2 \cdot 4 = 8 = s_3$。这行得通，所以我们不做任何改变。
接下来，$i = 4$。$c(4) = c_1 \cdot s_{4-1} = 2 \cdot 8 = 16 \neq 13 = s_3$。我们需要调整。如果我们令 $c = \{13 / 8\}$ 会怎样？问题是，现在 $c(4) = 13$ 就像我们想要的那样，但是 $c(3)$ 是错误的！我们不能再假设线性递归的长度仅为 1。我们需要更复杂的东西。
让我们更具体地说明我们想要什么。我们想要某个序列 $c' = c + d$ 使得 $c'(i)$ 对所有 $i \leq 4$ 的计算正确。 所以我们想要某个 $d$ 使得 $d(i) = 0$ for $i < 4$ 和 $d(4) = s_4 - c(4) = -3$。我们将 $d(4)$ 的预期值表示为 $\Delta$。
Here’s the trick to generate such a $d$: let’s keep track of each previous version of $c$ and which index it failed on. So for example, we have $\{\}$ which failed at index 0 and $\{1\}$ which failed at index 1. Let’s consider the second version of $c$, the $\{1\}$ sequence that failed at index 1. Let’s denote the failure index as $f$. Here’s what we’ll do:
- Set $d$ equal to that sequence.
- Multiply the sequence by $-1$.
- Insert a 1 on the left.
- Multiply the sequence by $\frac{\Delta}{d(f + 1)} = \frac{-3}{1} = -3$.
- Insert $i - f - 1 = 4 - 1 - 1 = 2$ zeros on the left.
$d$ after each step
After Step 1: $d = \{1\}$
After Step 2: $d = \{-1\}$
After Step 3: $d = \{1, -1\}$
After Step 4: $d = \{-3, 3\}$
After Step 5: $d = \{0, 0, -3, 3\}$
所以我们有 $d = \{0, 0, -3, 3\}$。这看起来很随意，但让我们计算 $d$ 看看会发生什么：
\[d(4) = d_1 s_{4-1} + d_2 s_{4-2} + d_3 s_{4-3} + d_4 s_{4-4} = 0 \cdot 8 + 0 \cdot 4 - 3 \cdot 2 + 3 \cdot 1 = -3\]
对于 $i < 4$，$d$ 是未定义的，因为它是长度为 4 的序列。所以我猜这 $d$ 有效。因此，我们的新递推是 $c + d = \{2\} + \{0, 0, -3, 3\} = \{2, 0, -3, 3\}$.
Let’s keep going. Our new $c$ will work for $i = 5$ and $i = 6$, but fail for $i = 7$.
\[c(7) = c_1 s_{7-1} + c_2 s_{7-2} + c_3 s_{7-3} + c_4 s_{7-4} = 2 \cdot 28 + 0 \cdot 20 - 3 \cdot 13 + 3 \cdot 8 = 41 \neq 215 = s_7\]
We need some $d$ to add to $c$ such that $d(i) = 0$ for $i < 7$ and $d(7) = s_7 - c(7) = 174$.
Once again, let’s look at the past versions of $c$:
- $\{\}$ which failed at index 0.
- $\{1\}$ which failed at index 1.
- $\{2\}$ which failed at index 4.
This time, we’ll consider the third version of $c$, the $\{2\}$ sequence that failed at index 4 (I’ll explain which version you pick in a moment). We will apply the following seemingly arbitrary steps:
- Set $d$ equal to our chosen sequence.
- Multiply the sequence by $-1$.
- Insert a 1 on the left.
- Multiply the sequence by $\frac{\Delta}{d(f + 1)} = \frac{174}{-3} = -58$.
- Insert $i - f - 1 = 7 - 4 - 1 = 2$ zeros on the left.
$d$ after each step
After Step 1: $d = \{2\}$
After Step 2: $d = \{-2\}$
After Step 3: $d = \{1, -2\}$
After Step 4: $d = \{-58, 116\}$
After Step 5: $d = \{0, 0, -58, 116\}$
我们的 $d$ 有效吗？让我们验证。
\begin{align*}
d(7) &= d_1 s_{7-1} + d_2 s_{7-2} + d_3 s_{7-3} + d_4 s_{7-4} = 0 \cdot 28 + 0 \cdot 20 - 58 \cdot 13 + 116 \cdot 8 = 174 \\
d(6) &= d_1 s_{6-1} + d_2 s_{6-2} + d_3 s_{6-3} + d_4 s_{6-4} = 0 \cdot 20 + 0 \cdot 13 - 58 \cdot 8 + 116 \cdot 4 = 0 \\
d(5) &= d_1 s_{5-1} + d_2 s_{5-2} + d_3 s_{5-3} + d_4 s_{5-4} = 0 \cdot 13 + 0 \cdot 8 - 58 \cdot 4 + 116 \cdot 2 = 0 \\
d(4) &= d_1 s_{4-1} + d_2 s_{4-2} + d_3 s_{4-3} + d_4 s_{4-4} = 0 \cdot 8 + 0 \cdot 4 - 58 \cdot 2 + 116 \cdot 1 = 0
\end{align*}
天哪，这真的有效！ 所以我们将 $d$ 添加到旧的 $c$ 以获得新的 $c$：$\{2, 0, -3, 3\} + \{0, 0, -58, 116\} = \{2 , 0, -61, 119\}$。
最后，我们处理 $i = 8$ 和 $i = 9$，发现递归对它们都是正确的。所以 $c = \{2, 0, -61, 119\}$ 是我们的最终答案。 | 
