Finding a general formula for a summation with discrete chain rule

Question

I'm trying to find a general formula for the summation $$\sum_{k=1}^{n} \frac{k+1}{2^k}$$ I think I can use the discrete chain rule to do this, but I'm only able to figure out some of the steps. Here's what I've done:

Discrete chain rule: $$\Delta(f(n)g(n))=\Delta f(n)g(n+1)+f(n) \Delta g(n)$$ where $$\Delta f(n)= \Delta f(n+1)-f(n)$$ $$f(k)=k+1, \Delta f(k+1)-f(k)=k+2-(k+1)=1$$ $$g(k)=\frac{1}{2^k}, \Delta g(k)=g(k+1)-g(k)=\frac{1}{2^{k+1}}-\frac{1}{2^k}=\frac{-1}{2^{k+1}}$$ Plugging it all in to the chain rule, we have, $$\Delta (f(k)g(k))=1*\frac{1}{2^k+1}+(k+1)*\frac{-1}{2^k+1} = \frac{1}{2^{k+1}}-\frac{k+1}{2^{k+1}}$$ Then, $$\sum_{k=1}^n \frac{k+1}{2^k}= \sum_{k+1}^n f(k) \Delta g(k)$$ The last thing I have is, $$\sum_{k+1}^n \Delta (f(k)g(k)) = \sum_{k+1}^n \frac{1}{2^{k+1}}+\sum_{k+1}^n \frac {-k-1}{2^{k+1}}$$ I'm not sure how to complete the rest.

Answer 1

Letting $$f(k) = k+1,\qquad g(k)=\frac{-1}{2^{k-1}},$$ then $$ \Delta f(k) = 1,\qquad \Delta g(k) = \frac1{2^k} $$ Therefore, \begin{align} \sum_{k=1}^n\frac{k+1}{2^k} &=\sum_{k=1}^nf(k)\cdot \Delta g(k) \\&=\sum_{k=1}^n\Delta(f(k)g(k))-(\Delta f(k)) g(k+1) \\&=\sum_{k=1}^n\Delta\Big(\frac{-(k+1)}{2^{k-1}}\Big)\quad-\quad\sum_{k=1}^n\frac{-1}{2^{k}} \\&=\sum_{k=1}^n\Big(\frac{-(k+2)}{2^k}-\frac{-(k+1)}{2^{k-1}}\Big)\quad+\quad\sum_{k=1}^n\frac1{2^{k}} \end{align} Now the first series is telescoping, and the second is geometric.

By the way, this is the discrete product rule, not chain rule.

Answer 2

We may use following function:

$S=2x +3x^2+4x^3+ . . .$

integrating we get:

$$\int S=x^2+x^3+x^4+ . . .x^n=\frac{x^{n-1}-1}{x-1}-1-x$$

Taking derivative of RHS we get:

$$S=\frac{(n-1)x^{n-2}.(x-1)-(x^{n-1}-1)-(x-1)^2}{(x-1)^2}$$

Now calculate S for $x=1/2$