Induction. $\forall k\in \Bbb N , \sum^{2k-1}_{n=k}\frac{n}{2^n}=\frac{(2k+2)2^k-4k-2}{2^{2k}}$

Question

$$\forall k\in \Bbb N , s_k=\sum^{2k-1}_{n=k}\frac{n}{2^n}$$ I have to show that : $$s_k=\frac{(2k+2)2^k-4k-2}{2^{2k}}$$I think that induction is needed there. I've checked that it's true for $k=1$ but I have absolutely no idea what should I do next.

Answer 1

Proof By Induction

The statement can be verified to be true for $k=1$. Let it be true for $k$. Now, $$s_{k+1}=\sum_{n=k+1}^{2k+1}\frac{n}{2^n}=s_k-\frac{k}{2^k}+\frac{2k}{2^{2k}}+\frac{2k+1}{2^{2k+1}}=\frac{(2k+2)2^k-4k-2}{2^{2k}}+\frac{2k+1+4k-k2^{k+1}}{2^{2k+1}}\\=\frac{(2k+2)2^{k+1}-8k-4+2k+1+4k-k2^{k+1}}{2^{2k+1}}\\=\frac{(2k+4)2^{k+1}-4k-6}{2^{2k+2}}$$ Hence the induction hypothesis is true.

Proof By Observation

$$s_k=\sum_{n=k}^{2k-1}\frac{n}{2^n}\implies 2s_k=\sum_{n=k}^{2k-1}\frac{n-1+1}{2^{n-1}}=\frac{k-1}{2^{k-1}}+s_k-\frac{2k-1}{2^{2k-1}}+\sum_{n=k}^{2k-1}\frac{1}{2^{n-1}}\\\implies s_k=\frac{(k-1)2^k-2k+1}{2^{2k-1}}+\frac{1-\frac{1}{2^{k}}}{2^{k-1}(1-\frac{1}{2})}\\=\frac{(k-1)2^k-2k+1+2(2^k-1)}{2^{2k-1}}$$From which the result follows.

Answer 2

the use of induction can be sidestepped in this case by using an approach in the spirit of a generating function. specifically, define: $$ S_n(x) = \sum_{k=0}^n \left( \frac{x}2 \right)^k \tag{1} $$ differentiating: $$ S'_n(x)=\sum_{k=1}^n \frac{k}2\left( \frac{x}2 \right)^{k-1} $$ the sum you require is: $$ S'_{2k-1}(1) -S'_{k-1}(1) $$ the key to the solution is therefore to use the geometric progression formula to obtain an expression for the sum $S_n(x)$ in (1), which you may then differentiate explicitly to get the expression for $S'_n(x)$. since

$$ S_n(x) = \frac{1-\left( \frac{x}2 \right)^{n+1}}{1-\frac{x}2} $$ we have: $$ (1-\frac{x}2)^2 S'_n(x) = -\frac{n+1}2 \left( \frac{x}2 \right)^n + \frac12 \left(1-\left( \frac{x}2 \right)^{n+1}\right) $$ and, setting $x=1$, and simplifying the fractions: $$ S_n'(1) = \frac{2^{n+1} - (n+2)}{2^n} $$ which gives: $$ S'_{2k-1}(1) -S'_{k-1}(1) = \frac{2^{2k} - (2k+1)}{2^{2k-1}}- \frac{2^{k} - (k+1)}{2^{k-1}} $$ or: $$ \frac{2^{k}(k+1) -(2k+1)}{2^{2k-1}} $$