Use induction to show that $\sum_{i=1}^k 2^{i-1} (k-i) = 2^k -k -1, k\ge1$

Question

This is an exercise question in Fundamentals of Computer Algorithms by Horowitz and Sahni. The base case for this is trivial. However for the inductive case, we need to verify, $p(n) \implies p(n+1)$ is true.

In the above summation, plugging in the values, with $i=k$, the term evaluates to $2^{k-1} (k-k)$ which evaluates to $0$. Regardless of the number of terms, the last term of the series is $0$. I was trying to evaluate the inductive step, however, was unable to proceed further.

I am not looking for a full solution, just hints and pointers to proceed further.

Answer 1

Hint

The induction should be on $k$ not on $i$. The index $i$ is just a dummy index used for summation. So assume that it is true for $k=n$ and then prove that it can be true for $k=n+1$.

Answer 2

What you need to show is that $$\sum_{i=1}^{k+1}2^{i-1}(k+1-i)=2^{k+1}-(k+1)-1$$ based on the fact that $\sum_{i=1}^{k}2^{i-1}(k-i)=2^{k}-k-1$.

Start by expanding the LHS:- $$\begin{align}\sum_{i=1}^{k+1}2^{i-1}(k+1-i)&=\sum_{i=1}^{k+1}[2^{i-1}(k-i)+2^{i-1}]\\&=\color{blue}{\sum_{i=1}^{k}2^{i-1}(k-i)}+2^{k}(-1)+\sum_{i=1}^{k+1}2^{i-1}\\&=\color{blue}{2^k-k-1}-2^k+\sum_{i=1}^{k+1}2^{i-1}\end{align}$$ Can you take it from here?