recurrence - 解决递归关系

Question

老实说，我什至不知道我这样做是否正确。这些问题要求解决：

C0 = 1

CN = CN/2 + N

当 N 是 2 的幂时。

这是我到目前为止所拥有的，但这是一个完整的猜测

CN = CN/2 + N

CN/2 = CN/4 + N/2

CN = CN/4 + N/2 + N

卡在这里

Answer 1

请注意，对于每个术语，您都在为下一个术语添加一些内容。因此，您将获得一笔款项。例如，对于 1024，您将获得：

1024 + 512 + 256 + 128 + 64 + 32 + 16 + ...

由于将非零数除以二永远不会产生零，因此永远不会达到基本情况 C0，并且您最终会得到一个无限级数。幸运的是，它是几何的。初始项为 N，每次乘以 1/2，因此总和将为 N/(1-1/2) = N/(1/2) = 2N。