系列AP GP clrs附錄附錄A.1-4

Question

我想證明CLRS練習冊中給出的方程。該公式是：

Sigma k=0 to k=infinity (k-1)/2^k = 0 

我解決了LHS，但我的答案是1，而RHS應該是0 以下是我的解決方案：

Let's say S = k/2^k = 1/2 + 2/2^2 + 3/2^3 + 4/2^4 .... 
2S = 1 + 2/2 + 3/2^2 + 4/2^3 ... 

2S - S = 1 + (2/2 - 1/2) + (3/2^2 - 2/2^2) + (4/2^3 -  3/2^3).. 
S = 1+ 1/2 + 1/2^2 + 1/2^3 + 1/2^4.. 
S = 2  -- eq 1 

Now let's say S1 = (k-1)/2^k = 0/2 + 1/2^2 + 2/2^3 + 3/2^4... 

S - S1 = 1/2 + (2/2^2 - 1/2^2) + (3/2^3 - 2/2^3) + (4/2^4 - 3/2^4).... 
S - S1 = 1/2 + 1/2^2 + 1/2^3 + 1/2^4... 
      = 1 
From eq 1 
2 - S1 = 1 
S1 = 1 

而所需的RHS爲0。這有什麼錯用我的解決方案？謝謝..

Answer 1

是的，您在解決問題方面存在問題。

儘管在編制S的值時所有內容都是正確的，但您已經錯誤地計算了S1的值。你錯過了在S1中代入k = 0的值。而對於S，即使在把k的值之後，第一項將是0，所以沒有效果。

因此，

S1 = (k-1)/2^k = -1 + 0/2 + 1/2^2 + 2/2^3 + 3/2^4... 
// you missed -1 here because you started substituting values from k=1 
S - S1 = -(-1) + 1/2 + (2/2^2 - 1/2^2) + (3/2^3 - 2/2^3) + (4/2^4 - 3/2^4).... 
S - S1 = 1 + (1/2 + 1/2^2 + 1/2^3 + 1/2^4...) 
     = 1 + 1 
     = 2. 

From eq 1 
2 - S1 = 2 
S1 = 0.